Множества

Как известно, в Отеле скучно не бывает: то фуршет, то номерки какие-то загадочные. А вот сейчас, для гостей опять подготовили нечто невероятное: приезжает Звезда.

Звезды — народ причудливый, вот например, Звезда, приехавшая в Отель, боится больших скоплений людей, поэтому поклонников на автограф-сессии будет принимать в специальном кабинете и только по одному, все же остальные гости будут ожидать в зале. И все бы хорошо, человечество давно придумало очереди, только вот во время сессии проходит фуршет, поэтому все разбредутся по залу и никакой очереди в ее привычном понимании устроить не получится и САО (служба администрирования очередей) решила обратиться к вам.

Вас просят написать систему учета людей, которая должна уметь выводить номер текущего первого в очереди гостя, добавлять людей в очередь и удалять из нее. Но мало того, что неразбериха с фуршетом, САО ещё и по неизвестной нам причине поощряет использование знакомств и связей в личных корыстных целях (в народе <<блат>>): если в зал приходит человек \(x\), то он хочет найти своего друга \(y\) и, если \(y\) находится в зале, то \(x\) в очереди становится прямо за ним, иначе \(x\) помещается системой в конец очереди. Также может произойти такое, что гостю надоело ждать и тогда он просто уходит из зала ожидания и исключается из очереди.

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

1. in x y — в зал фуршета приходит гость с номером \(x\), который дружит с гостем номер \(y\). Если \(y\) уже находится в очереди, то \(x\) встает за ним, иначе в конец. Стоит отметить, что гости очень восхищаются Звездой и могут приходить и не по одному разу.

2. out x — гостю под номером \(x\) надоело ждать и он уходит (гарантируется, что в данный момент гость с таким номером находится в зале).

3. check — Звезда готова дать очередной автограф и САО хочет узнать, кто первый в очереди (после этого счастливец получит автограф и уйдет по своим делам). Если очередь пуста, выведите \(-1\).

Формат входных данных
В первой строке вводится единственное натуральное число \(q\) (\(1 \leq q \leq 200\,000\)) — количество запросов. Далее в \(q\) строках вводятся вышеописанные запросы. Все числа, содержащиеся в запросах натуральные и не превосходят \(10^8\).

Формат выходных данных
На каждый запрос \(check\) в отдельной строке выведете номер первого человека в очереди.

Два интернет-магазина продают товары. Маркетолог хочет найти:

1. Товары, которые продаются только в первом магазине

2. Товары, которые продаются только во втором магазине

Формат входных данных

В первой строке — число N (1 ≤ N ≤ 100000) — количество товаров первого магазина.

Во второй строке — N целых чисел — коды товаров первого магазина (1 ≤ код ≤ 1000000).

В третьей строке — число M (1 ≤ M ≤ 100000) — количество товаров второго магазина.

В четвёртой строке — M целых чисел — коды товаров второго магазина.

Формат выходных данных

Первая строка: товары только первого магазина (в порядке возрастания через пробел) или "NONE".

Вторая строка: товары только второго магазина (в порядке возрастания через пробел) или "NONE".

Два программиста, Алекс и Макс, решали задачи на соревновании. Жюри хочет узнать, какие задачи решил ровно один из них (не оба сразу).

Формат входных данных

В первой строке — число N (1 ≤ N ≤ 100000) — количество задач, решённых Алексом.

Во второй строке — N целых чисел — номера задач Алекса (1 ≤ номер ≤ 1000000).

В третьей строке — число M (1 ≤ M ≤ 100000) — количество задач, решённых Максом.

В четвёртой строке — M целых чисел — номера задач Макса.

Формат выходных данных

Номера задач, решённых ровно одним программистом (в порядке возрастания через пробел). Если таких нет — выведите "NONE".

Вика и Ника собирают марки. Они решили объединить свои коллекции для выставки. Нужно вывести все уникальные номера марок, которые есть хотя бы у одной из девочек.

Формат входных данных

В первой строке — число N (1 ≤ N ≤ 100000) — количество марок у Вики.

Во второй строке — N целых чисел — номера марок Вики (1 ≤ номер ≤ 1000000).

В третьей строке — число M (1 ≤ M ≤ 100000) — количество марок у Ники.

В четвёртой строке — M целых чисел — номера марок Ники.

Формат выходных данных

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

Два брата, Коля и Толя, написали списки желаемых подарков на Новый Год. Мама хочет узнать, какие подарки хочет только Коля (но не Толя), чтобы подарить их именно ему.

Формат входных данных

В первой строке — число N (1 ≤ N ≤ 100000) — количество подарков в списке Коли.

Во второй строке — N целых чисел — номера подарков Коли (1 ≤ номер ≤ 1000000).

В третьей строке — число M (1 ≤ M ≤ 100000) — количество подарков в списке Толи.

В четвёртой строке — M целых чисел — номера подарков Толи.

Формат выходных данных

Все номера подарков, которые хочет только Коля (в порядке возрастания через пробел). Если таких нет — выведите "NONE".

Два друга, Алиса и Боб, составили списки своих любимых чисел. Найди все числа, которые нравятся ОБОИМ друзьям. Числа в списках Алисы и Боба могут повторяться и не обязательно отсортированы.

Формат входных данных

В первой строке — число N (1 ≤ N ≤ 100000) — размер списка Алисы.

Во второй строке — N целых чисел — любимые числа Алисы (1 ≤ число ≤ 1000000).

В третьей строке — число M (1 ≤ M ≤ 100000) — размер списка Боба.

В четвёртой строке — M целых чисел — любимые числа Боба.

Формат выходных данных

Все общие числа в порядке возрастания через пробел. Если общих чисел нет — выведите "NONE".

Петя записывает ID своих друзей в социальной сети. Некоторые ID повторяются (когда друзья заходят несколько раз). Петя хочет получить список всех уникальных ID в отсортированном порядке от меньшего к большему.

Формат входных данных

В первой строке — число N (1 ≤ N ≤ 100000) — количество записей.

Во второй строке — N целых чисел — ID друзей (1 ≤ ID ≤ 1000000).

Формат выходных данных

Все уникальные ID в порядке возрастания через пробел.

Алексей, возможно, самый умный и при этом самый ленивый человек в мире. Сегодня он участвует в олимпиаде.

На олимпиаде участникам даны \(n\) задач, за правильное решение \(i\)-й задачи, участник получит \(a_i\) баллов, за неправильное решение баллов не дают. Дипломы призера дадут тем участникам, которые наберут хотя бы половину от суммарного числа баллов. Например, если на олимпиаде дано три задачи, стоимости которых в баллах равны \(1\), \(3\) и \(4\), соответственно, для получения диплома призера достаточно набрать четыре балла.

Алексей пришел на олимпиаду с целью получить диплом призера. При этом Алексей очень умен и может правильно решить любую задачу на олимпиаде. Но в то же время Алексей очень ленив и хочет решить как можно меньше задач.

Алексей настолько ленив, что даже задачи, которые он будет решать, выбирает лениво. Он хочет выбрать некоторую задачу с номером \(k\), а затем решать задачи с номерами \(k, k+1, k+2 \ldots\) до тех пор, пока ему не будет хватать баллов на диплом призера. Максимум, на что готов Алексей, это пропустить одну задачу и не решать ее, чтобы решить в итоге еще меньше задач.

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

Формат входных данных
В первой строке дано одно натуральное число \(n\) — количество задач на олимпиаде (\(1 \le n \le 10^5\)).

Во второй строке заданы \(n\) чисел \(a_1, a_2, \dots a_n\) — стоимости каждой задачи в баллах (\(1 \le a_i \le 10^9\)).

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

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

Во втором тесте достаточно решить только вторую задачу, набрав три балла.

Август и Беатриса играют в игру. Август загадал натуральное число от 1 до n. Беатриса пытается угадать это число, для этого она называет некоторые множества натуральных чисел. Август отвечает Беатрисе YES, если среди названных ей чисел есть задуманное или NO в противном случае. После нескольких заданных вопросов Беатриса запуталась в том, какие вопросы она задавала и какие ответы получила и просит вас помочь ей определить, какие числа мог задумать Август.

Первая строка входных данных содержит число n — наибольшее число, которое мог загадать Август. Далее идут строки, содержащие вопросы Беатрисы. Каждая строка представляет собой набор чисел, разделенных пробелами. После каждой строки с вопросом идет ответ Августа: YES или NO.

Наконец, последняя строка входных данных содержит одно слово HELP.

Вы должны вывести (через пробел, в порядке возрастания) все числа, которые мог задумать Август.

Паровозики стоят на железной дороге параллельно друг другу на параллельных участках пути. Условно весь участок железной дороги можно представить в виде числовой прямой. В этом случае i-й паровозик на данной числовой прямой покрывает некоторое количество заданных целых точек (от точки starti до точки endi, включая данные точки).

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

Входные данные
В первой строке записано число N - количество паровозиков на железной дороге. В следующих N строках записаны по 2 числа (starti, endi)  - тоски начала и конца i-го паровозика. 

Ограничения

1 <= N <= 100
1 <= starti <= endi <= 100

Выходные данные
Выведите ответ на задачу.
 

Примеры

3
3 6
1 5
4 7

7

Ограничения

• 1 <= длина массива nums1 и длина массива nums2 <= 1000
• 0 <= nums1i, nums2i <= 1000

Ограничения

• 1 <= длина массива nums1 и длина массива nums2 <= 1000
• 0 <= nums1i, nums2i <= 1000

Примеры

3
4 9 5 
5
9 4 9 8 4

5 8

Ограничения

• 1 <= длина массива nums1 и длина массива nums2 <= 1000
• 0 <= nums1i, nums2i <= 1000

Примеры

3
4 9 5 
5
9 4 9 8 4

5

Ограничения

• 1 <= длина массива nums1 и длина массива nums2 <= 1000
• 0 <= nums1i, nums2i <= 1000

Ограничения

• 1 <= длина массива nums1 и длина массива nums2 <= 1000
• 0 <= nums1i, nums2i <= 1000

Примеры

3
4 9 5 
5
9 4 9 8 4

4 9

Примеры

1 5 4 2 5 6 6 2 3 3 5 2
2 3 5 1 2 1 2 6 7 1 1 6
1 4 6 8 8 7 0 6 0 3 8 1

9 10

Примеры

Входные данные
В первой строке записано натуральное число n - количество карточек у каждого ребенка. В каждой из трех следующих строк записаны по n неотрицательных целых чисел, не превышающих 10, разделенных пробелом. Во второй строке - числа на карточках Маши, в третьей - Даши, в четвертой - Миши.

Выходные данные
Выведите на экран одну строку - множество чисел в порядке возрастания, разделенных пробелами, которые встречаются, но не более чем у двоих из ребят.

Примеры

4
0 8 9 5 
6 7 3 7 
4 3 5 5

0 3 4 5 6 7 8 9

3
1 2 3
1 2 3
4 5 6

1 2 3 4 5 6