Степан, любитель настільних ігор, нещодавно відкрив для себе гру Robots. Гра складається з дошки з ~n~ рядків і ~m~ стовпців і одного робота. Поле (1, 1) є верхнім лівим полем дошки, тоді як поле (~n, m~) є нижнім правим.

На початку робот розташовується на якомусь полі ~(x,y)~ (~x~-й рядок, ~y~-й стовпець), і гравець може направляти його в одному з чотирьох напрямків: вгору, вниз, вліво або вправо. Залежно від обраного напрямку, він буде рухатися в цьому напрямку, поки не зустріне свою ціль або спеціальне поле на дошці. Якщо в будь-який момент він на краю дошки і хоче вийти з дошки, він обертається на іншу сторону дошки. Наприклад, якщо він знаходиться на полі (~n, 3~) і хоче рухатися вниз, він прибуде на поле (1, 3).

На дошці є три типи полів:

• Порожнє поле - робот продовжує рух у тому ж напрямку
• Поле повороту вліво - коли робот ступить на це поле, він поверне ліворуч на 90° і продовжить рух
• Поле повороту вправо - коли робот наступить на це поле, він повернеться вправо на 90° і продовжить рух

Більшість полів на дошці порожні, лише ~k~ з них є полями повороту ліворуч або праворуч.

Гра складається з ~q~ раундів. В ~і~-му раунді гри робот буде розміщений на полі (~a_i,b_i~). Мета полягає в тому, щоб досягти поля (~c_i,d_i~), використовуючи мінімальну кількість ходів, або визначити, що це зробити неможливо.

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

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

Формат вхідних даних

У першому рядку записано цілі числа ~n~, ~m~ і ~k~ (~1 ≤ n, m ≤ 10^6~, ~0 ≤ k ≤ 10^5~), кількість рядків, стовпців і непорожніх полів на дошці.

~i~-й із наступних ~n~ рядків містить цілі числа ~x_i,y_i~ та символ ~s_i~ (~1 ≤ x_i ≤ n~,~1 ≤ y_i ≤ m~,~s_i = ʼLʼ~ або ~s_i = ʼRʼ~), рядок і стовпець ~i~-го поля й тип повороту. Якщо ~s_i = «L»~, то слід повернути ліворуч. Якщо ~s_i = «R»~, то це поле повороту праворуч.

Наступний рядок містить ціле число ~q~ (~1 ≤ q ≤ 3 · 10^5~), кількість раундів.

~I~-й із наступних ~q~ рядків містить цілі числа ~a_i, b_i, c_i, d_i~(~1 ≤ a_i, c_i ≤ n~, ~1 ≤ b_i, d_i ≤ m~), стартову позицію та цільову клітину.

Формат вихідних даних

В ~i~-му з наступних ~q~ рядків вивести мінімальну кількість ходів для ~i~-го раунду гри або -1, якщо неможливо досягти мети.

Оцінювання

• тести 1-3 - 0 балів
• тести 4-7 - 10 балів ~k=0~
• тести 8-21 - 15 балів ~n,m≤300,q≤10~
• тести 22-35 - 45 балів ~n,m ≤ 300~
• тести 36-47 - 30 балів Жодних додаткових обмежень.

Приклад вхідних даних

2 2 2
1 1 L
2 2 R
5
1 1 2 2
2 1 1 2
1 1 1 2
2 1 1 1
2 2 2 1

Приклад вихідних даних

-1
1
0
0
0

Приклад вхідних даних

3 3 4
1 1 L
1 3 L
2 1 L
3 3 L
7
1 1 3 3
3 3 2 1
3 1 2 2
2 3 1 2
2 3 3 1
1 2 3 2
3 3 2 2

Приклад вихідних даних

1
2
1
1
1
0
3

Приклад вхідних даних

4 4 8
1 1 R
1 3 L
2 2 R
2 4 L
3 1 L
3 3 L
4 2 L
4 4 L
7
1 2 1 4
2 2 3 4
4 4 3 2
4 1 4 4
4 2 3 1
1 2 2 3
2 4 2 3

Приклад вихідних даних

2
1
1
0
-1
5
0