Задача A. Королевская династия ≡

Условие

Глеб очень любит историю. Он приходит в полный восторг, когда ему предлагают изучить историю какой-либо конкретной династии. Глеб очень строго относится к чистоте крови, поэтому при анализе династии он включает в рассмотрение только мужчин, которые являются кровными потомками основателя династии по отцовской линии.

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

Династия представляет собой множество людей, один из которых называется основателем династии, а любой другой представитель династии U имеет отца V, являющегося представителем династии. При этом U является сыном V, или потомком U через 1 поколение. Потомком U через k+1 поколение называется сын V некоторого потомка U через k поколений.

Глеба интересует информация о том, сколько у некоторого представителя династии V существует потомков через k поколений. Разумеется, Глеба интересует далеко не один такой вопрос.

В первом запросе тестового примера у представителя династии номер 1 есть два потомка во 2 поколении: 3 и 5.

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

В первой строке входного файла содержится одно число n — количество человек в династии, которую исследует Глеб (1 ≤ n ≤ 10⁵), представители династии пронумерованы различными натуральными числами от 1 до n. Далее следуют n чисел, i-е из которых задает номер отца i-го представителя династии, или равно −1, если соответствующий представитель является основателем династии.

Гарантируется, что основатель династии ровно один, и что любой упомянутый представитель династии является потомком основателя династии.

В следующей строке содержится число m — количество вопросов, которое интересует Глеба (1 ≤ m ≤ 10⁵). Далее следует m строк, каждая из которых содержит два целых числа v и k (1 ≤ v ≤ n, 1 ≤ k ≤ 10⁹) — номер исследуемого представителя династии и интересующее Глеба число поколений.

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

Для каждого вопроса выведите одно число — количество потомков через соответствующее число поколений у заданного представителя династии.

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

5
-1 1 2 1 4
2
1 2
4 7

2
0

Задача B. Палиндромные числа ≡

Условие

Вася очень любит изучать разные интересные классы чисел. Сегодня он изучает палиндромные числа.

Вася называет число палиндромным, если оно записывается одинаково слева направо и справа налево. При этом, Вася разрешает приписывать к числу несколько (возможно ни одного) лидирующих нулей. Например, числа 22, 4554, 12321, 5050 являются палиндромными. В частности, к числу 5050 необходимо приписать один ноль, чтобы получить 05050, которое читается одинаково слева направо и справа налево.

В числе прочих, Васю интересуют палиндромные числа, отличающиеся на 2. Для их исследования Вася рассматривает такие x, что x−1 и x+1 являются палиндромными. Такие числа Вася называет междупалиндромными. Вася хочет найти количество междупалиндромных чисел x от L_k до R_k включительно для нескольких отрезков [L_k, R_k].

Помогите Васе в этом нелегком деле!

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

Входной файл содержит несколько отрезков, которые интересуют Васю. В первой строке задано одно число T (1 ≤ T ≤ 2 000) — количество отрезков. В каждой из следующих T строк заданы два числа L_k и R_k (1 ≤ L_k ≤ R_k ≤ 10¹⁸) — границы отрезка.

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

Выведите T строк. В k-ой строке выведите одно число — количество междупалиндромных чисел в отрезке от L_k до R_k включительно.

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

3
18 23
21 21
50 55

1
1
0

Задача C. Супрематизм ≡

Условие

Недавно на уроках ИЗО Казимиру рассказали о различных направлениях искусства. Больше всего его впечатлил супрематизм, и он решил нарисовать свою первую картину в этом стиле.

Казимир помнил, что в супрематизме картина состоит из простых фигур, поэтому, сначала он нарисовал прямоугольник n × m, составленный из разноцветных квадратов 1 × 1. После критического переосмысления своего творения, Казимир пришел к выводу, что получившаяся картина слишком сложна, и не все смогут понять его задумку. Второго холста у него не было, и он решил исправлять эту картину. На достаточно простой картине, по мнению Казимира, должен присутствовать всего один цвет.

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

Помогите Казимиру определить, cможет ли он с помощью этих операций исправить свою картину и сделать ее достаточно простой.

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

В первой строке заданы два числа n и m (1 ≤ n, m ≤ 300) — размеры картины. Далее, в n~строках задано по m чисел c_i,j (1 ≤ c_i,j ≤ 1 000 000) — цвета квадратов, из которых составлена картина. Гарантируется, что на картине представлено хотя бы два цвета.

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

Если Казимиру не удастся сделать картину достаточно простой, выведите Poor Kazimir.

Иначе, выведите в первой строке k — количество действий, которое нужно сделать Казимиру. Действия могут быть двух видов:

• R r — перекрасить строку r (1 ≤ r ≤ n).
• C c — перекрасить столбец c (1 ≤ c ≤ m).

Разрешается сделать не более 1000 действий.

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

3 3
1 1 2
2 1 1
2 2 2

5
R 1
R 2
C 1
C 2
C 3

3 3
1 1 2
2 1 1
2 2 2

4
C 1
C 3
R 1
R 2

2 2
1 2
3 4

Poor Kazimir