Всеукраїнська олімпіада

Обмеження: 2 сек., 256 МіБ

Діти! Вітаємо вас із тим, що ви успішно потрапили в команду Львівської області, що поїде на Всеукраїнську олімпіаду з інформатики 2016 року. Зичимо вам великого успіху на змаганні і людських умов проживання в Хмельницькому.

На шляху до перемоги на Всеукраїнській олімпіаді у вас стоять не лише два тури змагань, а й багато інших, на перший погляд, нікчемних завдань. Перед олімпіадою вам треба щоранку прокидатися, чистити зуби, снідати, охайно вдягатися, причісуватися, ... Всього і не перелічити!

Одним із таких завдань є наступне: маючи деякий математичний вираз із дужками, вам необхідно вказати порядок, у якому будуть обчислюватися значення виразу в дужках.

Допоможіть же собі, напишіть для цього програму.

Вхідні дані

Єдиний рядок містить математичний вираз \(s\), що складається з цифр (0, 1, ..., 9), математичних операцій (+, -, /, *) та дужок ((, )). Не гарантується, що математичний вираз буде коректно побудований, або матиме зміст, проте гарантується, що дужки в виразі будуть коректно розставлені (для кожної відкриваючої дужки буде відповідна їй закриваюча, і навпаки).

Вихідні дані

Перший рядок повинен містити єдине натуральне число \(n\) — кількість пар дужок, що присутні в виразі. Наступні \(n\) рядків повинні містити пари натуральних чисел — позиції відкриваючої та відповідної їй закриваючої дужки (індексація починається з 1) в такому порядку, в якому вони будуть обчислені.

Обмеження

\(40\%\) тестів: \(2 \le |s| \le 10^3\),

\(60\%\) тестів: \(2 \le |s| \le 10^5\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4+((7-4)+(4+4))*(7-4)	4 4 8 10 14 3 15 17 21

Примітки

Дужки обчислюються зліва направо. Якщо якась пара дужок містить в собі інші дужки, то спочатку повинні бути обчислені всі внутрішні дужки, і тільки тоді обчислюються зовнішні.