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

Дмитрик може виконувати роботу в будь-якому порядку. Яку найбільшу кількість справ він зможе виконати за вказаний проміжок часу?

Обмеження

• ~1 \le T \le 10^5~
• ~1 \le t_i \le 10^5~
• ~1 \le C \le 100~

Input

Перший рядок вхідних даних складається з цілого числа ~T~ - час на виконання роботи.

Другий рядок містить ціле число ~C~ - загальна кількість робіт, які Дмитрик може вибрати.

Наступні рядки містять ціле додатне число ~t_i~ - кількість хвилин, необхідних для виконання ~i~-ї роботи.

Output

Вивести максимальну кількість завдань, які Дмитрик зможе виконати вчасно.

Sample Input 1

6
3
3
6
3

Sample Output 1

2

Для заданого натурального числа ~N~, знайдіть два прості числа ~A~ та ~B~ такі, що ~N=\frac{A + B}{2}~.

Нагадуємо, що просте число — це ціле число ~P>1~, яке ділиться лише на 1 та P.

Наприклад, 2, 3, 5, 7 є першими простими числами, а 1, 4, 6 не є простими числами.

Input

Перший рядок вхідних даних містить ціле число ~T~ (~1 \le T \le 10^3~) - кількість тестів.

Кожен із наступних ~T~ рядків містить ціле число ~N~ (~2 \le N \le 10^6~).

Output

Для кожного тесту в окремому рядку виведіть шукані прості числа ~A~ і ~B~, що розділяються пропуском.

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

Sample Input 1

4
8
4
7
21

Sample Output 1

11 5
5 3
7 7
23 19

Notes

Існування простих чисел ~A~ і ~B~ таких, що ~N=\frac{A + B}{2}~ слідує із відомої у математиці гіпотези Гольдбаха. На сьогоднішній день вона не спростована, і, звісно, не доведена.

Дмитрик погано поводився на уроці, і вчитель вирішив його завантажити додатковою роботою. Він написав на дошці список із  N  двійкових чисел. Усі ці двійкові числа мають по ~B~ біт (допускаються початкові нулі). Учитель поставив завдання Дмитрику: відсортувати ці числа у неспадному порядку.

Дмитрик, звісно, знає про існування двійкових чисел, але, будучи в міру лінивим, він вирішив змінити деякі біти у цих числах так, щоб утворений список чисел став відсортованим. Він не буде додавати біти або їх видаляти, він лише змінить деякі 1 на 0 і деякі 0 на 1. Числа стануть іншими, але вчитель, навряд чи зверне на ці дрібниці увагу.

Яку мінімальну кількість бітів треба змінити Дмитрику, щоб отримати відсортований список чисел.

Обмеження

~1 \le N \le 1000~

~1 \le B \le 50~

Input

У першому рядку міститься два цілих числа ~N~, ~B~, які розділяються пропуском.

У наступних ~N~ рядках задаються двійкові ~B~-бітні числа.

Output

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

Sample Input 1

4 3
111
110
000
100

Sample Output 1

3

Sample Input 2

10 5
10010
11101
01011
01000
11100
00110
00110
10001
01101
01000

Sample Output 2

10

Notes

Щоб отримати відсортований список, Дмитрику треба змінити перший символ першого числа, другий символ другого числа та перший символ третього числа.

011
100
100
100

Боб вирішив відправитися на канікули по містам Байтоляндії. В Байтоляндії є ~n~ міст, Боб живе в місті з номером 1. Щоб пересуватися по містам в Байтоляндії, після реформи запустили проїзні на потяги. Проїзний з номером ~i~ можна купити в містах з номерами від ~l_i~ до ~r_i~ включно за ~p_i~ гривень, і поїхати в будь-які міста з номерами від ~cl_i~ до ~rl_i~ включно. Якщо Боб вже купив проїзний, то він може скористатися ним безліч разів з будь якого міста. Боб ще не вирішив, в яке саме місто йому відправитися, тому просить вас для кожного міста сказати мінімальну суму, яку потрібно витратити, щоб дістатися до нього.

Input

Перший рядок містить числа ~n~ і ~k (1 \le n, k \le 10^5)~ - кількість міст в Байтоляндії та кількість проїзних.

Наступні ~k~ рядків містять по 5 чисел - ~l_i, r_i, cl_i, rl_i, p_i (1 \le l_i \le r_i \le n, 1 \le cl_i \le cr_i \le n, 1 \le p_i \le 10^9)~ - проміжок міст, в яких можна купити проїзний з номером ~i~ та проміжок міст, в які можна поїхати з цим проїзним і його ціна.

Output

Для кожного міста виведіть мінімальну суму, яку потрібно витратити Бобу, щоб потрапити туди. Якщо Боб не може поїхати в це місто, то виведіть -1.

Scoring

1) ~l_i~ = ~r_i~, ~cl_j~ = ~cr_j~, для всіх ~i, j~
2) ~k, n \le 100~
3) ~k, n \le 1000~
4) ~\sum (cr_i - cl_i + 1) \le 2*10^5~
5) ~l_i = r_i~
6) без обмежень

Sample Input 1

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

Sample Output 1

0 -1 9 9 9 9 5 5

Боб вже рік займається танцями, тому він має виступити на шоу талантів. Він вже написав номер, але несподівано помітив, що в його записах є помилки. Боб починає танцювати біля лівої стіни і робить послідовні кроки вліво і вправо в деякому порядку так, щоб закінчити танець в тому самому місці, в якому Боб почав, і так, щоб не врізатися в стіну(тобто, якщо він стоїть в початковому місці, то не може зробити крок вліво).
Записи Боба - це послідовність з символів ~L~ і ~R~, які позначають рухи вліво і вправо відповідно. Щоб виправити свої записи, він може зробити декілька операцій, кожна з яких буде наступного вигляду:

• вибрати підрядок і циклічно зсунути його вправо(наприклад, "LRL" -> "LLR"),

• або поставити символ "L" або "R" в будь якому місці послідовності.

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

Input

Перший рядок містить число ~n~ ~(1 \le n \le 2*10^5)~ - довжина запису Боба.

Наступний рядок містить послідовність з літер "L" і "R" - його запис.

Output

Виведіть одне ціле число - суму важкості всіх підрядків запису Боба.

Sample Input 1

6
RLRLRL

Sample Output 1

15

Примітка

У першому прикладі є наступні підрядки:

• {L} -> {RL} - одна операція, таких підрядків є 3
• {R} -> {RL} - одна операція, таких підрядків є 3
• {RL} -> {RL} - нуль операцій
• {LR} -> {RL} - одна операція, таких підрядків є 2
• {RLR} -> {RLRL} - одна операція, таких підрядків - 2
• {LRL} -> {RLRL} - одна операція, таких підрядків - 2
• {LRLR} -> {RLRL} - одна операція
• {RLRL} -> {RLRL}
• {RLRLR} -> {RLRLRL} - одна операція
• {LRLRL} -> {RLRLRL} - одна операція
• {RLRLRL} -> {RLRLRL}

Відповідь буде наступною: ~1 \times 3 + 1 \times 3 + 1 \times 2 + 1 \times 2 + 1 \times 2 + 1 + 1 + 1 = 15~