п»ї
Фермер Джон и его \(Q\) (\(1 \leq Q \leq 2 \cdot 10^5\)) коров на Манхеттене.
Коровы сбежали и гуляют по городу. В Манхеттене \(N\) (\(1 \le N \le 2 \cdot 10^5\))
дорог проходящие бесконечно на \(x\)-\(y\)-плоскости. Все они расположены
или горизонтально, или вертикально. Каждая горизонтальная или вертикальная
может быть смоделирована уравнением вида \(y = c_i\) или \(x = c_i\), где \(c_i\)
целое число в интервале от \(0\) до \(10^9\) включительно.
ФД знает точно где каждая корова начала путешествие и время путешествия.
Каждая из коров движется по следующему шаблону:
- Она двигается на север (\(+y\)) или восток (\(+x\)) на одну единицу в секунду.
- Если она на одиночной дороге, она продолжает двигаться по ней.
- Если она на пересечении двух дорог, она идёт на север, на чётной секунде
путешествия и на восток иначе.
ВАм дана карта Манхэттена и информация о каждой корове, помогите ФД
где его коровы сейчас.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка ввода содержит
\(N\) Рё
\(Q\).
Следующие \(N\) строк описывают дороги.
Каждая дорога описывается направлением (H или V) координатой \(c_i\).
Гарантируется, что каждая дорога уникальна.
Следующие \(Q\) строк описывают коров.
Каждая корова описывается тремя целыми числами \((x_i, y_i, d_i)\),
означающими, что она начала путешествие из позиции \((x_i, y_i)\)
ровно \(d_i\) секунд назад. Гарантируется, что \((x_i, y_i)\) лежит
на некоторой дороге, и \(0 \le x_i, y_i, d_i \le 10^9\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите \(Q\) строк, где \(i\)-ая строка содержит текущую позицию i-ой коровы.
ПР�МЕРВВОДА:
4 5
V 7
H 4
H 5
V 6
6 3 10
6 4 10
6 5 10
6 6 10
100 4 10
ПР�МЕРВЫВОДА:
14 5
7 13
6 15
6 16
110 4
Первые две коровы прошли следующий путь:
(6, 3) -> (6, 4) -> (7, 4) -> (7, 5) -> (8, 5) -> ... -> (14, 5)
(6, 4) -> (6, 5) -> (7, 5) -> (7, 6) -> ... -> (7, 13)
ОЦЕН�ВАН�Е:
- Тесты 2-4 : \(N, Q, c_i, x_i, y_i, d_i \leq 100\).
- Тесты 5-9 : \(N, Q\le 3000\).
- Тесты 10-20 : Нет дополнительных ограничений.
Автор: Benjamin Qi