Бессі ховається десь на числовій прямій. Кожна з інших ~N~ корів Фермера Джона (~1\le N\le 1000~) має частину інформації: ~i~-та корова каже, що Бессі ховається у місці, меншому або рівному ~p_i~, або що Бессі ховається у місці, більшому або рівному ~p_i~ (~0\le p_i\le 10^9~).

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

Input

Перший рядок містить ~N~.

Наступні ~N~ рядків містять L або G, а потім ціле число ~p_i~. L означає, що ~i~-та корова каже, що місце приховування Бессі менше або дорівнює ~p_i~, а G означає, що ~i~-та корова каже, що місце приховування Бессі більше або дорівнює ~p_i~.

Output

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

Sample Input 1

2
G 3
L 5

Sample Output 1

0

Sample Input 2

2
G 3
L 2

Sample Output 2

1

Бессі знаходить рядок ~s~ довжиною не більше ~2\cdot 10^5~, який містить лише три символи 'C', 'O' та 'W'. Вона хоче дізнатися, чи можна перетворити цей рядок в одне єдине 'C' (її улюблений символ), використовуючи такі операції:

1. Оберіть два прилеглих однакових символи та видаліть їх.

2. Оберіть один символ та замініть його на два інших символи у будь-якому порядку.

Знаходження відповіді на самому рядку не є достатнім для Бессі, тому вона хоче знати відповідь для ~Q~ (~1 \le Q \le 2\cdot 10^5~) підрядків рядка ~s~.

Input

Перший рядок містить ~s~.

Наступний рядок містить ~Q~.

Наступні ~Q~ рядків кожен містить два цілих числа ~l~ та ~r~ (~1 \le l \le r \le |s|~, де ~|s|~ позначає довжину ~s~).

Output

Рядок довжиною ~Q~, де ~i~-й символ буде 'Y', якщо ~i~-й підрядок може бути скорочений, та 'N' у протилежному випадку.

Sample Input 1

COW
6
1 1
1 2
1 3
2 2
2 3
3 3

Sample Output 1

YNNNYN

Notes

Відповідь на перший запит - так, оскільки перший символ ~s~ вже дорівнює 'C'.

Відповідь на п'ятий запит - так, оскільки підрядок OW від другого до третього символу ~s~ може бути перетворений на 'C' за допомогою двох операцій:

   OW
-> CWW
-> C

Інші підрядки цього прикладного рядка COW не можуть бути скорочені до 'C'.

Бессі перебуває в 2D, де дозволено ходити лише у напрямках паралельних одній з координатних вісей. Вона починає з точки ~(0,0)~ і хоче дістатися до ~(N,N)~ (~1\le N\le 10^9~). Щоб допомогти їй, на сітці розташовано ~P~ (~1\le P\le 10^5~) трамплінів. Кожен трамплін знаходиться в фіксованій точці ~(x_1, y_1)~ і якщо Бессі використовує його, вона приземлиться в точці ~(x_2, y_2)~.

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

Input

Перший рядок містить два цілих числа, розділених пробілом, ~N~ та ~P~.

Наступні ~P~ рядків містять чотири цілих числа, ~x_1~, ~y_1~, ~x_2~, ~y_2~, де ~x_1 \le x_2~ та ~y_1 \le y_2.~

Усі місця для трамплінів і кінцеві точки є різними.

Output

Виведіть одне ціле число, мінімальну відстань, яку повинна пройти Бессі, щоб дістатися ~(N,N)~.

Оцінювання

Для ~28\%~ балів виконується обмеження ~P \le 1000~.

Sample Input 1

3 2
0 1 0 2
1 2 2 3

Sample Output 1

3

Notes

Найкращий шлях Бессі:

• Бессі йде з (0,0) до (0,1) (1 одиниця).

• Бессі стрибає на (0,2).

• Бессі йде з (0,2) до (1,2) (1 одиниця).

• Бессі стрибає на (2,3).

• Бессі йде з (2,3) до (3,3) (1 одиниця).

Загальна довжина шляху Бессі складає 3 одиниці.

Бесі стала художницею та створює картини печер! Її поточна робота у процесі - це сітка висоти ~N~, така що кожен ряд сітки містить точно ~M~ квадратів (~1\le N,M\le 1000~). Кожний квадрат може бути порожнім, заповненим скельною породою або водою. Бесі вже намалювала квадрати, які містять скельну породу, включаючи весь контур картини. Тепер вона хоче заповнити деякі порожні квадрати водою так, що якщо б картина була реальною, не було б жодного руху води. Визначається висота квадрата у ~i~-му рядку від верху як ~N + 1-i~. Бесі хоче, щоб її картина задовольняла наступне обмеження:

Припустимо, що квадрат ~a~ заповнений водою. Тоді, якщо існує шлях від ~a~ до квадрата ~b~ за допомогою лише порожніх або водяних квадратів, які не вище за ~a~, так що кожні два сусідні квадрати на шляху мають спільну сторону, то ~b~ також заповнений водою.

Знайти кількість різних картин, які може зробити Бесі за модулем ~10^9+7~. Бесі може заповнити будь-яку кількість порожніх квадратів водою, включаючи нуль або всі.

Input

Перший рядок містить два числа ~N~ та ~M~, розділені пробілом.

Наступні ~N~ рядків введення містять кожен ~M~ символів. Кожен символ це - '.' або '#', що представляє порожній квадрат та квадрат, заповнений скельною породою, відповідно. Перший та останній рядок та перший та останній стовпець містять тільки '#'.

Output

Одне ціле число: кількість картин, що задовольняють обмеженням, за модулем ~10^9+7~.

Оцінювання

В ~40\%~ балів ~N, M\le 10~.

Sample Input 1

4 9
#########
#...#...#
#.#...#.#
#########

Sample Output 1

9

Notes

Якщо квадрат у другому рядку заповнений водою, то всі порожні квадрати повинні бути заповнені водою. В іншому випадку, припустимо, що нічим не заповнені такі квадрати. Тоді Бесі може обрати заповнити будь-яку підмножину трьох горизонтально розташованих областей порожніх квадратів у третьому рядку. Таким чином, кількість картин дорівнює ~1 + 2^3 = 9.~