Граючись у своєму улюбленому текстовому редакторі, Даніель вирішив намалювати картинку висотою ~N~ символів та шириною ~M~ символів. Картинка складається виключно з символів "." та *, причому символи * утворюють деякі прямокутники, що не перетинаються. Прямокутники навіть не торкаються один одного сторонами чи кутами.

Допоможіть Даніелю порахувати кількість прямокутників.

Input

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

Кожен з наступних ~N~ рядків містить ~M~ символів "." або *, які представляють намальовану Даніелем картинку.

Всі * формують прямокутники, які не доторкаються та не перетинаються.

Output

В одному рядку виведіть кількість прямокутників на картинці.

Оцінювання

У тестових випадках загальною вартістю 20 балів усі прямокутники складатимуться з одного символу *. У тестових випадках вартістю додаткових 30 балів виконуватиметься умова ~N=1~.

Sample Input 1

6 7
***....
***..**
.....**
.***.**
.***...
.***...

Sample Output 1

3

Sample Input 2

3 3
*.*
...
*.*

Sample Output 2

4

Sample Input 3

1 10
.*.**.***.

Sample Output 3

3

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

Навіть сьогодні, після майже 20 років, новий політик є гостем у кожному епізоді шоу, де йому повідомляють, хто звинуватив його у поганому стані країни. Цей політик потім звинувачує іншого політика, і порочне коло продовжується. Щоб зробити все цікавішим, ми ексклюзивно дізналися, що кожен політик має фіксовану стратегію поведінки під час шоу. Точніше, кожен політик знає, кого звинуватити, базуючись на тому, хто звинуватив його у попередньому шоу. Ми надамо вам цю інформацію і сподіваємося, що ви зможете написати програму, яка обчислює, який політик буде гостем ~K~-го шоу.

Input

Перший рядок містить цілі числа ~N(2 \leq N \leq 500)~ та ~K(1 \leq K \leq 10^{18})~ з опису задачі.

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

Можна припустити, що жоден політик ніколи не звинуватить себе. Тому жодне з чисел у ~i~-му рядку матриці не буде дорівнювати ~i~. Аналогічно, зауважте, що ~i~-те число в ~i~-му рядку матриці завжди буде дорівнювати 0 і може бути проігнороване.

Output

В одному рядку ви повинні вивести номер політика, який буде гостем ~K~-го епізоду ток-шоу.

Оцінювання

У тестових випадках загальною вартістю 49 балів буде виконуватися умова ~1 \leq K \leq 10^{5}~.

Sample Input 1

2 4
0 2
1 0

Sample Output 1

2

Sample Input 2

3 7
0 3 2
3 0 3
2 1 0

Sample Output 2

1

Sample Input 3

4 7
0 4 3 2
4 0 4 1
2 1 0 1
3 2 3 0

Sample Output 3

3

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

Адвент-календар можна представити як таблицю з ~n~ рядків та ~m~ стовпців. Кожна клітинка містить маленьке віконце, а за кожним віконцем знаходиться шматочок шоколаду. Славко вже відкрив деякі віконця, а інші все ще закриті.

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

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

Input

Перший рядок містить цілі числа ~n~ та ~m~ ~(1 \leq n \leq 1000, 1 \leq m \leq 10)~ - розміри адвент-календаря.

Кожен з наступних ~n~ рядків містить ~m~ символів "." та #, що представляють адвент-календар. Символ "." позначає відкрите віконце, а символ # позначає закрите віконце.

Output

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

Оцінювання

1. (~25~ балів): Кожне закрите віконце прилягає (має спільну сторону) максимум до двох інших закритих віконець;

2. (~35~ балів): ~n \leq 10~;

3. (~40~ балів): без додаткових обмежень.

Паула любить готувати смажені страви. Щоб зробити страву якомога смачнішою, їй потрібно розрізати послідовність з ~n~ цілих чисел на сегменти з максимальною загальною вартістю.

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

Наприклад, якщо ми розріжемо послідовність ~[1, 4, 1, 5, 3, 6]~ на сегменти ~[1, 4, 1]~ та ~[5, 3, 6]~, загальна вартість буде ~(4-1)+(6-3)=6~.

Буде ~q~ оновлень виду "додати ~x~ до елементів з індексами ~l, l+1, \ldots, r~". Після кожного оновлення дайте відповідь на запит "Яка максимально можлива вартість розрізаної послідовності?".

Input

Перший рядок містить цілі числа ~n~ та ~q~ ~(1 \leq n, q \leq 200000)~, довжину послідовності та кількість оновлень.

Другий рядок містить ~n~ цілих чисел ~a_i~ ~(-10^8 \leq a_i \leq 10^8)~, послідовність, яку Паула має розрізати.

Кожен з наступних ~q~ рядків містить цілі числа ~l~, ~r~ ~(1 \leq l \leq r \leq n)~ та ~x~ ~(-10^8 \leq x \leq 10^8)~, що описують оновлення.

Output

Виведіть ~q~ рядків, максимально можливу вартість послідовності після кожного оновлення.

1. (~21~ бал): ~1 \leq n, q \leq 200~;

2. (~30~ балів): ~1 \leq n, q \leq 3000~;

3. (~49~ балів): без додаткових обмежень.

Sample Input 1

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

Sample Output 1

2
2
0

Sample Input 2

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

Sample Output 2

2
1
3