Степан збирається бігти марафон. Дистанція включає ~N~ контрольних пунктів, які треба відвідати почергово від 1 до  ~N~. Він зараз не в формі і хоче пропустити один контрольний пункт (не 1 і не  ~N~, звичайно).

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

Примітка. Відстань між двома точками (~x_1,y_1~) та (~x_2,y_2~) манхетенська: ~|x_1-x_2| + |y_1-y_2|~, оскільки рухатися можна лише паралельно осям координат.

Input

Перший рядок вхідного файлу містить ціле число ~N~ (~1 \le N \le 10^5~)

Наступні ~N~ рядків містять цілі числа ~x_i, y_i~ (~-1000 \le x_i,y_i \le 1000~).

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

Числа у рядках розділяються пропуском.

Output

У вихідний файл вивести шукану мінімальну відстань.

Sample Input 1

4
0 0
8 3
11 -1
10 0

Sample Output 1

14

Notes

Слід пропустити точку (8,3) і отримаємо мінімальну відстань 14.

Задається сітка кросворда розміром ~N \times M~. Деякі комірки порожні (на кросворді вони зазвичай білі), а деякі позначені решіткою (на кросворді вони чорні). На кросворді відсутні номери слів, і Вам їх треба відновити, використовуючи такі логічні кроки:

• крок 1: Для кожної комірки визначаємо, чи вона є горизонтальним загаданим словом, чи вертикальним. Щоб це було горизонтальне слово, то треба, щоб комірка зліва була чорною або межею кросворда, а дві клітинки справа були вільними - мінімальна довжина слова дорівнює 3. Правила для вертикального слова аналогічні: зверху має бути чорна клітинка або межа, а вниз - дві або більше вільних клітин.
• крок 2: Призначаємо кожній комірці номер, який починає слово, послідовно від 1 у тому порядку, в якому ми читаємо книгу. В першому рядку призначаємо числа зліва-направо, потім у другому і т.д. Числа призначаємо тільки тим коміркам, де починається слово.

Input

Перший рядок вхідного потоку містить цілі числа ~N, M~ (~3 \le N, M \le 50~)

Наступні ~N~ рядків містять по ~M~ символів: крапку або решітку.

Output

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

Наступні рядки містять координати комірок із числами у порядку їх зростання. Верхня ліва комірка має координату (1,1), а права нижня - (~N,M~)

Sample Input 1

5 3
...
#..
...
..#
.##

Sample Output 1

4
1 1
1 2
1 3
3 1

Notes

Кросворд для прикладу буде таким:

123
#..
4..
..#
.##

Плямистість корів

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

На жаль, ФД не вдало зібрав дані про своїх корів. Для кожної з його ~N~ корів, все, що він знає, це вага корови і має чи ні вона плями. Усі його корови мають різну вагу. За цими даними він побудував те, що він назвав "класифікатор найближчого сусіда". Щоб вгадати, є у нової корови C пляма чи ні, він спочатку знаходить у своєму стаді корову С' таку, що її вага найближча до C. Якщо корова C' має плями, то ФД припускає, що корова C має плями, якщо корова C' немає плям, то ФД передбачає, як і корова C немає плям. Якщо ж унікального найближчого сусіда немає, а є дві корови на однаковій мінімальній відстані від C, тоді ФД передбачає, що корова C має плями, якщо одна з двох найближчих корів також є плями.

ФД хоче перевірити свій автопровісник плямистості на групі нових корів, які тільки-но прибули на його ферму. Після зважування нових корів він виявив, що вони мають вагу всіх цілих чисел в інтервалі від ~A~ до ~B~ включно.

Будь ласка, визначте, скільки з цих корів будуть класифіковані як такі, що мають плями. Зауважимо, що класифікатор робить прогноз, ґрунтуючись на даних про ~N~ існуючих корів. Також зауважимо, що ~A~ і ~B~ можуть бути досить великими числами, так що просто перевірка всіх чисел по одному від ~A~ до ~B~ не пройде по часу.

Input

Перший рядок вхідного потоку містить цілі числа ~N, A, B~ (~1 \le N \le 5 \times 10^4~, ~1 \le A \le B \le 10^9~)

Наступні ~N~ рядків описують одну корову. Кожен рядок містить або S W, що означає, що корова з вагою W має плями або NS W, що означає, що корова з вагою W не має плям. (~1 \le W \le 10^9~).

Числа у рядках розділяються пропуском.

Output

У вихідний потік вивести одне ціле число - кількість корів із прибулих, яких алгоритм ФД класифікує як плямисті.

Sample Input 1

3 1 10
S 10
NS 4
S 1

Sample Output 1

6

Марафон-2

Степан збирається бігти марафон. Дистанція включає ~N~ контрольних пунктів, які треба відвідати почергово від 1 до  ~N~. Він зараз не в формі і хоче пропустити ~K~ контрольних пунктів (не 1 і не  ~N~, звичайно).

Допоможіть Степану знайти мінімальну відстань, яку йому треба пробігти, якщо він пропустить до ~K~ контрольних пунктів.

Примітка. Відстань між двома точками (~x_1,y_1~) та (~x_2,y_2~) манхетенська: ~|x_1-x_2| + |y_1-y_2|~, оскільки рухатися можна лише паралельно осям координат.

Input

Перший рядок вхідного файлу містить цілі числа ~N, K~ (~1 \le K < N \le 10^5~)

Наступні ~N~ рядків містять цілі числа ~x_i, y_i~ (~-1000 \le x_i,y_i \le 1000~).

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

Числа у рядках розділяються пропуском.

Output

У вихідний файл вивести шукану мінімальну відстань.

Sample Input 1

5 2
0 0
8 3
1 1
10 -5
2 2

Sample Output 1

4

Notes

У прикладі, показаному тут, пропуск контрольних точок при (8, 3) і (10, -5) призводить до мінімальної сумарної відстані 4.

Степан спланував марафон, специфікувавши ~N~ контрольних точок, які слід послідовно відвідати.

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

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

Оскільки марафон проходить на вулицях Манхеттена, то відстань між двома точками (~x_1,y_1~) та (~x_2,y_2~) манхетенська: ~|x_1-x_2| + |y_1-y_2|~.

Input

Перший рядок вхідного файлу містить цілі числа ~N, Q~ (~1 \le N,Q \le 10^5~).

Наступні ~N~ рядків містять цілі числа ~x_i, y_i~ (~-1000 \le x_i,y_i \le 1000~). Контрольні пункти задаються у тому порядку, в якому їх треба відвідати.

Далі ідуть ~Q~ рядків, які містять запити по одному у рядку:

- рядки мають формат: "U I X Y" або "Q I J". Рядок "U I X Y" вказує, що положення точки з номером ~I~ (~1 \le I \le N~)  має бути змінено на (~X,Y~). Рядок "Q I J" опитує мінімальну відстань проходження маршруту від контрольної точки ~I~ до контрольної точки ~J~ (~I \le J~), з врахуванням того, що учасники можуть пропустити одну контрольну точку цього підмаршруту (крім точок ~I~ і ~J~).

Числа у рядках розділяються пропуском.

Output

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

Sample Input 1

5 5
-4 4
-5 -3
-1 5
-3 4
0 5
Q 1 5
U 4 0 1
U 4 -1 1
Q 2 4
Q 1 4

Sample Output 1

11
8
8