Задача A. Вспомогательный вопрос Вселенной ≡

Условие

Как вы возможно знаете, ученые уже нашли Главный вопрос жизни, Вселенной и вообще, и он таков: "Сколько будет шестью девять?". Не удовлетворившись этим, ученые наняли маленькую Магратеанскую фирму построить мини-компьютер, чтобы найти какой-нибудь более узкий вопрос (они назвали его вспомогательным), который теоретически может пролить свет на жизнь, Вселенную и что-нибудь еще.

Этот компьютер построили, но к сожалению результат вычисления был поврежден и частично потерян. Наконец, создателям компьютера удалось получить строку, которая является частью правильного вопроса. После тщательного анализа, конструкторы подумали, что исходный результат может быть построен из строки добавлением к ней некоторых букв без перестановки и удаления исходных букв. Они также полагают, что правильный результат — это арифметическое выражение (как и Главный вопрос), но поскольку вопрос вспомогательный, он не содержит умножения, только сложение. Более точно, он должен соответствовать грамматике на рисунке.

Помогите им дать что-нибудь своим клиентам. Они попросили вас восстановить вопрос на основе поврежденного ответа компьютера, который им удалось получить.

Формат входного файла

Формат выходного файла

Примеры тестов

1+0+1)

(1+0+1)

2009

2009

)(()(

(0)+((0)+(0))

Задача B. Бюрократия ≡

Условие

Давным давно в одном далеком королевстве король решил записывать все законы королевства. С тех пор, когда появлялся новый закон, соответствующую запись добавляли в архив законов.

Много веков спустя юристы обнаружили, что в королевстве было только два вида законов:

• прямой закон, который устанавливает новые правила;
• отменяющий закон, который отменяет один из предыдущих законов.

Закон считается активным если и только если нет активного закона, отменяющего его.

Ваша задача — написать программу, которая определяет, какие законы до сих пор активны.

Формат входного файла

Первая строка входного файла содержит целое число n (1 ≤ n≤ 10⁵) — число изданных законов.

Следующие n описывают по одному закону каждая. Каждое описания удовлетворяет одному из следующих форматов:

• declare, означает, что издан новый закон.
• cancel i, где i — номер закона, отменяемого данным.

Законы нумеруются с единицы.

Формат выходного файла

Примеры тестов

5
declare
cancel 1
declare
cancel 2
cancel 3

3
1 4 5

Задача C. Круги на экране ≡

Условие

Вчера Андрей написал программу, которая рисует n белых кругов на черном экране. Экран монохромный и его разрешение — w × h пикселей. Пиксели нумеруются от верхнего левого угла (0, 0) к правому нижнему (w−1, h−1).

Круг с центром в пикселе (x_c, y_c) и радиусом r состоит из пикселей с координатами (x, y) такими, что √(x_c − x)² + (y_c − y)² ≤ r. Если круг не влазит в экран, он обрезается. Если пиксель принадлежит двум и более кругам, он белый.

Картинка получилась очень красивая, поэтому Андрей решил скопировать ее н стену. У него белые обои, поэтому он может только раскрасить часть стены черным. Теперь он хочет знать, сколько ему потребуется краски. Он копирует картинку точно пиксель в пиксель, поэтому вам надо написать программу, которая вычисляет число черных пикселей, оставшихся на экране после рисования n кругов.

Формат входного файла

В первой строке входного файла содержится три целых числа: w, h, и n (1 ≤ w, h ≤ 20000; 1 ≤ n ≤ 100). Каждая из последующих n строк содержит описания кругов. В i+1-ой строке находится три целых числа: x_i, y_i, r_i (0 ≤ x_i < w; 0 ≤ y_i < h; 0 ≤ r_i ≤ 40 000). Они обозначают круг с центром в пикселе (x_i, y_i) и радиусом r_i.

Замечание: картинка соответствует второму примеру.

Формат выходного файла

Вам нужно вывести ровно одно число — количество черных пикселей, оставшихся на экране.

Примеры тестов

5 3 2
1 1 1
3 1 1

6

12 9 2
3 3 2
7 5 4

51

Задача D. Вопрос дракона ≡

Условие

Шли три брата и встретили дракона. Дракон задал им задачку: "назовите положительное целое число, которое делится на d и имеет ровно n цифр, полагая, что d равно сорока пяти, а n равно трем!"

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

Формат входного файла

Во входном файле ровно одна строка с целыми числами n и d (1 ≤ n ≤ 1000; 1 ≤ d ≤ 1 000 000).

Формат выходного файла

Первая и единственная строка выходного файла должна содержать ответ на вопрос дракона — или число из n цифр (без лидирующих нулей), делящееся на d или строку "No solution".

Примеры тестов

20 1

10000000000000000000

1 23

No solution

1 4

4