Пройшло три роки, і Ладіслав повернувся до Рутенії. За час його перебування далеко від дому він став борцем проти забобонів.

Тепер він любить лише числа в 13-ковій системі числення, які не починаються з 3. Він також не переносить цифри 4 та 7 взагалі, а ще більше не витримує числа, де сусідні цифри однакові.

Відомо, що колись він любив n-ті числа в різних системах числення.

З нагоди його повернення, Серхіо хоче подарувати Ладіславу n-те число його дивної системи. Але з такою кількістю правил він заплутався, тому просить вас допомогти йому знайти це число.

13-кова система числення має цифри ('0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c').

Input

В єдиному рядку задане число ~n~ ~(1 \le n \le 10^{100000}).~

Output

Виведіть n-те число системи Ладіслава.

Sample Input 1

7

Sample Output 1

a

Notes

Перші 7 чисел у системі Ладіслава виглядають так:

1, 2, 5, 6, 8, 9, a

Sample Input 2

10

Sample Output 2

10

Ромео дуже любить ducks DAGs, а ще більше він любить ігри на ducks DAGs.

Сьогодні він вигадав нову гру і вирішив запропонувати Анастасієті зіграти в неї.

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

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

Input

У першому рядку задано ~t~ ~(1 \le t \le 300)~ — кількість партій, які зіграють Ромео та Анастасієта.

Далі задається опис кожної з ~t~ партій:

У першому рядку для кожної партії задано три цілі числа ~n~, ~m~, ~k~ ~(1 \le n, m, k \le 3 \cdot 10^5)~ —– кількість вершин, ребер у графі, а також кількість фігур, розміщених на графі.

У другому рядку задано ~k~ цілих чисел ~v_i~ ~(1 \le v_i \le n)~ —– вершини, на яких розміщені фігури.

У наступних ~m~ рядках записані по два числа ~v_i~, ~u_i~ ~(1 \le v_i, u_i \le n)~, які означають, що в графі є ребро з вершини ~v_i~ до вершини ~u_i~.

Гарантується, що заданий граф є ациклічним, а суми ~n~ та ~m~ для всіх партій не перевищують ~3 \cdot 10^5~.

Output

Для кожної партії виведіть "Romeo", якщо для перемоги Ромео слід почати першим, і "Anastasieta" —– в протилежному випадку. Імена виведіть без лапок.

Sample Input 1

3
3 2 2
1 3
1 2
3 2
4 4 2
1 4
1 2
1 3
2 3
4 3
11 12 4
1 4 7 11
1 2
1 3
2 3
4 3
4 5
5 6
7 8
8 9
7 9
9 10
11 5
11 8

Sample Output 1

Anastasieta
Romeo
Anastasieta

У вас є шахова дошка нескінченного розміру, на якій розміщено ~n~ тур (ROOKs). Ладіслав — професійний шахіст і дуже не любить ситуацій, коли тури атакують одна одну. Тому йому стало цікаво, яку мінімальну кількість тур він повинен прибрати, щоб жодна з них не атакувала іншу, маючи координати всіх тур.

Тури атакують на будь-яку кількість клітинок по горизонталі та вертикалі.

Input

На вхід подається ціле число ~n~ ~(1 \le n \le 10^5)~ — кількість тур (ROOKs), що розміщені на шаховій дошці.

В наступних ~n~ рядках вводяться два числа ~x_i~, ~y_i~ ~(-10^9 \le x_i, y_i \le 10^9)~ — координати ~i~-ої тури. Гарантується, що дві тури не можуть стояти на одній клітинці.

Output

Вивести мінімальну кількість тур, яких потрібно прибрати Ладіславу з дошки.

Sample Input 1

6
1 1
1 3
1 4
3 1
3 4
4 4

Sample Output 1

3

Всі знають, що Серхіо подобається Julia (це така мова програмування, не вірите — перевірте самі), а Julia любить математику.

Серхіо хоче покорити Julia's процесор, для цього йому слід знайти кількість масивів ~a~ довжини ~n~, таких, що сума їх елементів дорівнює ~sum~, і при цьому виконується умова: ~0 \le a_1 \le a_2 \le \dots \le a_n~.

Допоможіть Серхіо підкорити Julia's процесор і знайти кількість таких масивів.

Оскільки кількість масивів може бути дуже великою, виведіть відповідь по модулю ~10^9+7~.

Input

В єдиному рядку задано два цілі числа ~n~ та ~sum~ ~(1 \le n,~ ~sum \le 2\cdot10^4)~ — кількість елементів масиву ~a~ та їхня сума.

Output

Виведіть одне ціле число — кількість масивів ~a~, які задовольняють умову.

Sample Input 1

2 3

Sample Output 1

2

Sample Input 2

4 4

Sample Output 2

5

Sample Input 3

1024 256

Sample Output 3

564310539

Notes

Тест 1: є 2 способи вибрати такий масив, а саме: 0, 3, 1, 2.

Тест 2: є 5 способів вибрати такий масив, а саме: 0, 0, 0, 4, 0, 0, 1, 3, 0, 0, 2, 2, 0, 1, 1, 2, 1, 1, 1, 1.

Ромео знає, що Анастасіета дуже CHARівна, і подарунок має бути не менш CHARівний.

В нього є послідовність ~s~, що складається з ~n~ рядків, пронумерованих числами ~1, 2, \dots, n~. Кожен рядок має певну CHARівність, яка дорівнює числу ~a_i~.

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

Рядок ~t~ є префіксом рядка ~s~, якщо ~|t| \le |s|~ та для всіх ~i \in \{1,2,3,\dots,|t|\}~ ~s[i] = t[i]~ (за умови, що символи нумеруються, починаючи з ~1~).

Знайдіть максимальну суму значень ~a_i~ вибраних рядків.

Input

У першому рядку знаходиться одне число ~n~ (~1 \le n \le 2 \cdot 10^5~) — кількість рядків.

У другому рядку знаходяться ~n~ цілих чисел ~a_i~ (~0 \le a_i \le 10^9~) — CHARівності рядків.

У кожному з наступних ~n~ рядків знаходиться один рядок ~s_i~. Кожен рядок складається тільки з малих латинських літер.

Гарантується, що сумарна довжина рядків не перевищує ~5 \cdot 10^5~, тобто ~\sum_{i=1}^{n}|s_i| \le 5 \cdot 10^5~.

Output

Виведіть одне ціле число — максимальну суму вартостей.

Sample Input 1

5
1 2 3 4 5
aa
a
abb
s
aba

Sample Output 1

13

Sample Input 2

4
10 4 3 1
aa
aas
abb
s

Sample Output 2

14