D2. Побег на Бобракторе
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
512 мегабайт
ввод
stdin
вывод
stdout

Хватит это терпеть! Умный Бобер решил устроить побег из академгородка Бобруйской Академии Наук (БАН). БАН представляет собой квадрат b × b на плоскости, ему принадлежат точки с координатами x, y (0 ≤ x, y ≤ b). А чтобы путь прошел быстрее и веселее, наш Умный Бобер соорудил из отечественных пиломатериалов Бобрактор — удобное и эффективное транспортное средство.

На территории академгородка существуют правила дорожного движения — n стрелок, параллельные осям координат. Эти стрелки не пересекаются и не касаются друг друга. Когда Бобрактор доезжает до какой-нибудь стрелки, то он поворачивается в направлении этой стрелки и продолжает свое движение либо до тех пор, пока не доедет до следующей стрелки, либо пока не покинет пределы академгородка. За одну единицу времени Бобрактор преодолевает ровно одну единицу расстояния. Можно считать, что для Бобрактора не существует никаких других препятствий.

Академики БАН хотят отправить новенький Бобрактор в НИИ «Академтрактор», а самого Умного Бобра — в аспирантуру, точить карандаши. У них есть q планов, представляющих собой потенциальное стартовое положение Бобрактора (xi, yi), начальный вектор движения wi и время ti, прошедшее с начала побега.

Необходимо для каждого из q планов определить, где будет находиться Умный Бобер через заданное время.

Входные данные

В первой строке содержится два целых числа: количество правил дорожного движения n и размер академгородка b, 0 ≤ n, 1 ≤ b. В последующих n строках указаны сами правила. Каждая строка правил содержит четыре целых числа x0, y0, x1, y1, разделенных одиночными пробелами — начало и конец стрелки. Гарантируется, что все стрелки параллельны осям координат и не имеют общих точек. Все стрелки находятся внутри академгородка, то есть выполняется 0 ≤ x0, y0, x1, y1 ≤ b.

В последующей строке содержится целое число q — количество планов академиков, 1 ≤ q ≤ 105: i-ый план представляет собой два целых числа, xi, yi — координаты Бобрактора в начальный момент времени, 0 ≤ xi, yi ≤ b, символ wi, принимающий значение U, D, L, R и задающий начальное направление вверх, вниз, влево или вправо соответственно (ось Y направлена вверх), а также ti — время, прошедшее с начала побега, 0 ≤ ti ≤ 1015.

  • для получения 30 баллов требуется решить задачу при n, b ≤ 30 (подзадача D1);
  • для получения 60 баллов требуется решить задачу при n, b ≤ 1000 (подзадачи D1+D2);
  • для получения 100 баллов требуется решить задачу при n, b ≤ 105 (подзадачи D1+D2+D3).
Выходные данные

Выведите q строк. В каждой строке должно содержаться два числа — координаты Бобрактора в конечный момент времени для каждого из планов. Если Умный Бобер успеет покинуть академгородок за время ti, то выведите координаты последней точки, которую он посетил внутри академгородка.

Примеры
Входные данные
3 3
0 0 0 1
0 2 2 2
3 3 2 3
12
0 0 L 0
0 0 L 1
0 0 L 2
0 0 L 3
0 0 L 4
0 0 L 5
0 0 L 6
2 0 U 2
2 0 U 3
3 0 U 5
1 3 D 2
1 3 R 2
Выходные данные
0 0
0 1
0 2
1 2
2 2
3 2
3 2
2 2
3 2
1 3
2 2
1 3