Зіг і Заг грають у словесну гру. Зіг називає одну літеру, а Заг називає слово, яке починається з цієї літери. Однак слово має бути зі списку дозволених слів і таке, яке Заг вже сказав найменшу кількість разів. Якщо вибір слова неоднозначний, тоді Заг вибере те, яке лексикографічно менше (раніше за алфавітом). Для кожної літери Зіга буде можливо вибрати слово.

Нехай є список, що складається з рівно ~K~ різних слів та масив з ~N~ літер, які назвав Зіг. Напишіть програму, яка на основі вхідних даних виведе масив з ~N~ слів, які сказав Заг під час гри.

Input

Перший рядок вхідних даних містить додатні цілі числа ~K~ (~1 \leq K \leq 100,000~) та ~N~ (~1 \leq N \leq 100,000~) із задачі.

Кожен з наступних ~K~ рядків містить одне слово, що складається з малих літер англійського алфавіту довжиною не більше 21 символа.

Кожен з наступних ~N~ рядків містить одну малу літеру англійського алфавіту.

Output

Ви повинні вивести ~N~ рядків, кожен з яких містить одне слово із задачі.

У тестових випадках вартістю 60% від загальної кількості балів буде виконуватися умова, що ~N~ та ~K~ не більші за 500.

Sample Input 1

4 5
zagreb
split
zadar
sisak
z
s
s
z
z

Sample Output 1

zadar
sisak
split
zagreb
zadar

Sample Input 2

5 3
london
rim
pariz
moskva
sarajevo
p
r
p

Sample Output 2

pariz
rim
pariz

Sample Input 3

1 3
zagreb
z
z
z

Sample Output 3

zagreb
zagreb
zagreb

Чи мріяли ви колись, що ви головний герой комп'ютерної гри? Головний герой цієї історії, Бранімір, саме зараз бачить такий сон.

Світ у сні Браніміра складається з ~N~ хмарочосів, розташованих зліва направо. Для ~i~-го хмарочоса нам відома висота ~H_i~ та кількість золотих монет ~G_i~ на даху хмарочоса. Гра починається зі стрибка на будь-який з хмарочосів і складається з кількох кроків. На кожному кроці Бранімір може стрибнути на хмарочос праворуч від того, на якому він зараз знаходиться (він також може перестрибнути через кілька з них), якщо він не нижчий за поточний. На кожному даху хмарочоса, де він опиняється, Бранімір збирає всі золоті монети.

Бранімір може закінчити гру після будь-якої кількості кроків (також нуль), але він повинен зібрати принаймні ~K~ золотих монет, щоб перейти на наступний рівень.

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

Input

Перший рядок вхідних даних містить додатні цілі числа ~N~ (~1 \leq N \leq 40~) та ~K~ (~1 \leq K \leq 4 \cdot 10^{10}~), числа із задачі.

~i~-й з наступних ~N~ рядків містить два додатні цілі числа, ~H_i~ та ~G_i~ (~1 \leq H_i, G_i \leq 10^9~), числа із задачі.

Output

Ви повинні вивести кількість різних способів зіграти в гру із задачі.

Оцінювання

У тестових випадках вартістю ~40\%~ від загальної кількості балів буде виконуватися ~N \leq 20~.

Sample Input 1

4 6
2 1
6 3
7 2
5 6

Sample Output 1

3

Sample Input 2

2 7
4 6
3 5

Sample Output 2

0

Sample Input 3

4 15
5 5
5 12
6 10
2 1

Sample Output 3

4

Нам дано дерево з ~N~ вершинами, позначеними різними додатніми цілими числами від 1 до ~N~. Додатково дано ~M~ пар вершин з дерева у вигляді ~(a_{1}, b_{1}),(a_{2}, b_{2}), \ldots,(a_{M}, b_{M})~. Потрібно направити кожне ребро дерева так, щоб для кожної заданої пари вершин ~(a_{i}, b_{i})~ існував шлях від ~a_{i}~ до ~b_{i}~ або від ~b_{i}~ до ~a_{i}~. Скільки різних способів це зробити? Оскільки відповідь може бути досить великою, визначте її за модулем ~10^{9}+7~.

Input

Перший рядок вхідних даних містить додатні цілі числа ~N~ та ~M(1 \leq N, M \leq 3 \cdot 10^{5})~, кількість вершин у дереві та кількість заданих пар вершин відповідно.

Кожен з наступних ~N-1~ рядків містить два додатніх цілих числа, номери вершин, з'єднаних ребром.

~i~-й з наступних ~M~ рядків містить два різних додатніх цілих числа ~a_{i}~ та ~b_{i}~, номери вершин з ~i~-ї пари вершин. Усі пари вершин будуть взаємно різними.

Output

Ви повинні вивести один рядок, що містить загальну кількість різних способів направити ребра дерева, які задовольняють вимогу з умови, за модулем ~10^{9}+7~.

У тестових випадках вартістю ~20\%~ від загальної кількості балів задане дерево буде ланцюгом. Іншими словами, вершина ~i~ буде з'єднана ребром з вершиною ~i+1~ для всіх ~i<N~.</p>

У додаткових тестових випадках вартістю ~40\%~ від загальної кількості балів буде виконуватися ~N, M \leq 5 \cdot 10^{3}~.

Sample Input 1

4 1
1 2
2 3
3 4
2 4

Sample Output 1

4

Sample Input 2

7 2
1 2
1 3
4 2
2 5
6 5
5 7
1 7
2 6

Sample Output 2

8

Sample Input 3

4 3
1 2
1 3
1 4
2 3
2 4
3 4

Sample Output 3

0

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

Вчора він знайшов у своєму гаражі послідовність із ~N~ натуральних чисел. Оскільки йому було дуже нудно, він вирішив зайняти себе простими запитами. Кожен запит може бути одного з двох типів:

1. Змінити значення на позиції ~X~ в послідовності на ~V~.

2. Визначити кількість цікавих неперервних підмасивів, що містяться в інтервалі ~[L, R]~ послідовності.

Input

Перший рядок вхідних даних містить числа ~N~ та ~Q(1 \leq N, Q \leq 10^{5})~, що представляють кількість елементів у послідовності та кількість запитів відповідно. Наступний рядок містить ~N~ натуральних чисел ~A_{i}(1 \leq A_{i} \leq 10^{9})~, які представляють числа в початковій послідовності.

Кожен з наступних ~Q~ рядків містить запит наступної форми:

* Перше число в рядку може бути 1 або 2 і представляє тип запиту.

* Якщо запит типу 1, слідують два числа, ~X(1 \leq X \leq N)~ та ~V(1 \leq V \leq 10^{9})~ із задачі.

* Якщо запит типу 2, слідують два числа, ~L~ та ~R(1 \leq L \leq R \leq N)~, що представляють ліву та праву межу інтервалу.

Output

Для кожного запиту типу 2 виведіть кількість цікавих неперервних підмасивів із задачі.

Sample Input 1

5 1
8 4 3 9 1
2 2 5

Sample Output 1

4

Sample Input 2

5 3
2 3 6 4 1
2 1 4
1 3 1
2 3 5

Sample Output 2

6
1

Sample Input 3

4 3
2 2 2 2
2 1 4
1 2 3
2 1 4

Sample Output 3

10
5