Хан не хотел учиться один, поэтому он пригласил своего друга Доминика позаниматься вместе с ним. После того, как они решили рекордное количество задач за вечер, Доминик поехал домой. Внезапно его остановила полиция, подозревая, что он водил в пьяном виде. Чтобы проверить Доминика, полицейские начали задавать ему вопросы.
Полицейский: Давайте начнём с чего-то простого. Какова асимптотика сортировки пузырьком?
Доминик: О, это просто. O ( n 2 ) .
Полицейский: Скажите английский алфавит наоборот.
Доминик: Легко, zyxwvutsrqponmlkjihgfedcba.
Полицейский: Вы просто запомнили это. Представьте, что строчные буквы латинского алфавита записаны по кругу по часовой стрелке. Начинайте с буквы 'a' и называйте все буквы подряд. После каждой сказанной буквы я могу приказать теперь называть в обратном порядке, спросить сколько раз была названа какая-то буква или ничего не делать. Приступайте.
Доминик: Хм... a, b, c...
Возможно, Доминик не настолько трезв, чтобы решить эту задачу. Помогите ему.
Первая строка содержит одно целое число Q ( 1 ≤ Q ≤ 10 5 ) – количество приказов полицейского. Каждая из последующих Q строк содержит один из приказов в формате "SMJER n" или "UPIT n x". Приказ первого типа обозначает, что после n -й сказанной буквы требуется поменять направление. Приказ второго типа обозначает, что Доминик должен сказать, сколько раз он произнес букву x после n сказанных букв.
Во всех запросах 1 ≤ n ≤ 10 9 , а x – строчные латинские буквы. В запросах n идут в строго возрастающем порядке.
Для каждого запроса вида "UPIT n x", выведите ответ на этот запрос, каждый в отдельной строке, в том же порядке, что и в вводе.
40 баллов: n ≤ 1000
60 баллов: n ≤ 10 5
100 баллов: n ≤ 10 9
В первом примере Доминик говорит a, b, c, d, c, b, a, z, y, x.
Во втором примере Доминик говорит a, z, a, z, y, x, w.
5 UPIT 1 b UPIT 3 b SMJER 4 UPIT 7 a UPIT 10 z
0 1 2 1
5 SMJER 1 SMJER 2 SMJER 3 UPIT 5 a UPIT 7 w
2 1
4 UPIT 100 a UPIT 200 c UPIT 300 a UPIT 400 b
4 8 12 16
Юный джедай Иван был заброшен на Звезду Смерти с заданием уничтожить её. Для того, чтобы уничтожить Звезду Смерти, ему требуется массив неотрицательных целых чисел a i длины N . К сожалению, у Ивана нет этого массива, но есть секретный документ с требованиями к этому массиву, который ему передал его старый друг Дарт Вейдер.
В этом документе содержится квадратная матрица m размера N , где элемент в i -й строке в j -м столбце равен побитовому "И" чисел a i и a j . Для повышения безопасности главная диагональ матрицы была уничтожена и вместо чисел на ней были записаны нули. Помогите Ивану восстановить массив a и выполнить свою миссию.
Гарантируется, что решение всегда существует. Если решений несколько, выведите любое.
В первой строке содержится число N ( 1 ≤ N ≤ 1000 ) – размер матрицы. Каждая из последующих N строк содержит по N целых чисел m ij ( 0 ≤ m ij ≤ 9 ) – элементы матрицы.
В единственной строке выведите N целых неотрицательных чисел, не превышающих 100 – требуемый массив a .
40 баллов — (1 ≤ N ≤ 5) .
100 баллов — (1 ≤ N ≤ 1 000) .
3 0 1 1 1 0 1 1 1 0
1 1 1
5 0 0 1 1 1 0 0 2 0 2 1 2 0 1 3 1 0 1 0 1 1 2 3 1 0
1 2 3 1 3