Задача А. "Чаювання в Хмеляндії"

   Типовий житель Хмеляндії Хмелюша вирів влаштувати собі чаювання. Він має в запасі нескінченно багато чаїв кожного з M сортів. Чаювання проходить наступним чином:
      1. Початково склянка Хмелюші повністю наповнена чаєм сорту 1.
      2. Наступні N разів Хмелюша випиває половину чаю у склянці, доливає до склянки чай сорту x_i так, щоб склянка знову була повністю наповнена і ретельно перемішує. Після останнього доливання він випиває повністю весь чай зі склянки. А тепер Хмелюшу цікавить наступне питання: а якого ж чаю він випив найбільше?

   Вхідні дані:
   В першому рядку вхідного потоку задаються числа 1 ≤ N ≤ 10⁵ i 1 ≤ M ≤ 10⁹ - кількість доливань, які буде робити Хмелюша і кількість сортів чаю, які наявні у нього. В наступному рядку вхідного потоку знаходяться N чисел - послідовність {x_i} (1 ≤ x_i ≤ M).

   Вихідні дані:
   Виведіть одне число - сорт чаю, якого Хмелюша випив найбільше. Якщо таких сортів кілька - виведіть той, номер якого найменший.

   Приклади

Задача В. "Мурахи на колі"

   В країні Хмеляндії дивина трапилася: мурахи почали танцювати... Є коло на якому позначено N відміток з номерами від 1 до N за годинниковою стрілкою. На колі знаходяться M мурашок. Жодні дві мурашки не стоять на одній і тій самій відмітці початково. Також відомо те, в якому напрямку кожна мурашка буде танцювати. Якщо під час танку дві мурашки зустічаються, то кожна з них починає танцювати в іншому напрямку. А ваше завдання неймовірно просте: скажіть, де знаходитимуться мурашки через T секунд такого танцю.

   Вхідні дані:
   Всі числа у вхідному потоці цілі. В першому рядку знаходяться числа 2 ≤ N ≤ 10⁹, 1 ≤ M ≤ 10⁵ i 1 ≤ T ≤ 10⁹. Наступні M рядків мають наступний формат: Кожен рядок містить два числа 1 ≤ x ≤ N, y належить {-1,1}. Перше число цього рядку x - позиція мурашки, друге число цього рядку y - напрям, у якому танцюватиме мурашка. y = 1, якщо мурашка починає танцювати за годинниковою стрілкою і y = - 1, якщо проти. Відстані між сусідніми відмітками однакові. За одну секунду мурашка долає відстань, яка рівна відстані між сусідніми відмітками на колі.

   Вихідні дані:
   В першому рядку виведіть M цілих чисел у порядку зростання - позиції, на яких знаходитимуться мурашки через T секунд після таких навіжених танців.

   Приклади

Задача С. "Хмелюша і матриці"

   На уроках Хмелюша частенько "літає в хмарах". Але одного разу до його вимріяного світу прийшло велике зло. Звісно, Хмелюша зовсім не хоче, щоб зло було в його світі, тому він почав шукати закляття, щоб звільнити його. Виявилось, що потрібно просто знайти кількість прямокутних підматриць даної матриці, щоб сума елементів у кожній такій підматриці була парна.

   Вхідні дані:
   Перший рядок вхідних даних: 1 ≤ N, M ≤ 2000 - розміри матриці. Наступні N рядків містять в собі по M чисел, відокремлених одиничними пробілами. Кожне число - натуральне, з відрізку [1, 10⁹]

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

   Приклади

Задача D. "Прямолінійність в Хмеляндії"

   Хмелюша – людина прямолінійна, тому від одразу запропонував вам наступне завдання. Нехай T₁ = 3, T₂ = 2, T₃ = 1. А загалом T_n = T_{n - 1} + T_{n - 2} + T_{n - 3}, коли n > 3. Порахуйте значення S = T²₁ + T²₂ + ... + T²_N. Рахувати це значення потрібно за модулем 10⁹ + 7 (Хмелюша терпіти не може довгі числа).

   Вхідні дані:
   У вхідному потоці задано одне число 1 ≤ N ≤ 10¹⁸.

   Вихідні дані:
   Вивести одне число S - відповідь до задачі.

   Приклади

Задача Е. "Гопник Вася"

   Гопнік Вася - дуже миролюбний гопнік з Хмеляндії. Однак він дуже агресивний до цифр. Всього є n пар цифр, за які Вася може надавати по чайнику, якщо побачить їх у одному числі підряд (зауважимо, (2, 1) і (1, 2) - різні пари). Хмелюша випадково зустрівся з Васею в темному провулку. І Вася, змилувавшись над Хмелюшою, сказав, що не буде його бити, якщо він скаже k-е по зростанню натуральне число, яке у нашого гопніка не викличе агресію. Допоможете бідному Хмелюші?

   Вхідні дані:
   У першому рядку задано число 1 ≤ t ≤ 100 - кількість зустрічей Хмелюші і Васі. Кожна зустріч задається в такому форматі: Спочатку задано число 0 ≤ n ≤ 100 - кількість пар чисел, які викликають у Васі агресію. У наступних n рядках йдуть по два числа - цифри, які в парі викликають агресію у Васі. Врахуйте, що пари можуть повторюватися. В останньому рядку знаходиться натуральне число 1 ≤ k ≤ 10¹⁸ – порядковий номер числа, що не викличе агресії у Васі і яке потрібно знайти.

   Вихідні дані:
   Вивести одне число - відповідь на задачу. Якщо число більше за 5 * 10¹⁸, потрібно вивести -1. (Вася не любить дуже великі числа)

   Приклади