Нечестная игра
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На клетчатой доске размером $$$n \times m$$$, состоящей из $$$n$$$ строк и $$$m$$$ столбцов, в клетке $$$(r, c)$$$, то есть на пересечении $$$r$$$-й сверху строки и $$$c$$$-го слева столбца, расположена фишка. На этой доске вам предстоит сыграть против компьютера в игру, в которой можно перемещать фишку и удалять клетки поля.

Каждый ход устроен следующим образом.

  1. Компьютер называет целое число $$$k > 0$$$.
  2. Вы ровно $$$k$$$ раз некоторым образом выбираете одну из еще не удаленных клеток, соседних по стороне (имеющих общую сторону) с той, в которой фишка находится в текущий момент, и перемещаете фишку в эту клетку. Вы можете перемещать фишку на клетку, в которой она уже была. Если не существует еще не удаленных клеток, соседних по стороне с текущей, перемещение не производится.
  3. Компьютер называет координаты $$$(i, j)$$$ произвольной еще не удаленной клетки поля, после чего она сразу же удаляется.

Если компьютер удаляет клетку, на которой находится фишка, игра заканчивается вашей победой. Ваша цель — победить как можно раньше. При этом вы не сообщаете компьютеру свои перемещения, поэтому можете играть нечестно: вместо реального перемещения фишки по полю вы можете следить за всеми возможными ее положениями. Иными словами, если в какой-то момент при удалении клетки $$$(i, j)$$$ существует последовательность перемещений фишки, при которой в данный момент фишка находится в точности в клетке $$$(i, j)$$$, вы можете сообщить компьютеру, что игра завершена, и вы победили.

Разумеется, компьютер следит за соблюдением правил, поэтому если вы сообщаете ему о своей победе при удалении клетки, на которой фишка не могла в этот момент находиться, вы автоматически проигрываете.

Определите как можно меньший номер хода, после которого вы можете сообщить комьютеру о своей победе, то есть после которого фишка могла оказаться на удаляемой клетке. Чем ближе ваш ответ к минимальному возможному, тем больше баллов вы получите.

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

В единственной строке ввода даны четыре целых числа $$$n$$$, $$$m$$$, $$$r$$$ и $$$c$$$ — размеры доски и координаты изначального расположения фишки ($$$1 \le r \le n \le 1000$$$; $$$1 \le c \le m \le 1000$$$).

Во второй строке ввода дано максимальное количество баллов, которое можно получить за соответствующую группу тестов. Ваше решение это значение может игнорировать.

В следующих $$$n \cdot m$$$ строках даны ходы, которые последовательно собирается сделать компьютер. Описание $$$t$$$-го хода задается тремя целыми числами $$$k_t$$$, $$$i_t$$$ и $$$j_t$$$ — количеством перемещений фишки, которые вам понадобится совершить, и координатами клетки поля, которую после этого требуется удалить ($$$1 \le k_t \le 10^9$$$; $$$1 \le i_t \le n$$$; $$$1 \le j_t \le m$$$).

Гарантируется, что все удаляемые клетки различны, то есть никакая клетка не удаляется дважды.

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

Выведите одно целое число от $$$1$$$ до $$$n \cdot m$$$ — номер хода, после которого вы сообщите компьютеру о своей победе.

Система оценки

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

То есть, если вы проигрываете игру на каком-либо тесте группы, вы получаете вердикт WA за соответствующий тест и $$$0$$$ баллов за всю группу. Иначе, если $$$R(\mathtt{group})$$$ — максимальное число баллов за группу, а $$$j(\mathtt{test})$$$ и $$$p(\mathtt{test})$$$ — ответы на тест программы жюри и вашей программы, соответственно, вы получаете за группу $$$$$$\left\lfloor R(\mathtt{group}) \cdot \min\limits_{\mathtt{test} \in \mathtt{group}} \frac{j(\mathtt{test})}{p(\mathtt{test})} \right\rfloor \text{ баллов.}$$$$$$

Обратите внимание, что прохождение тестов из условия не является необходимым для тестирования на некоторых группах тестов.

ПодзадачаБаллыОграничения Необходимые подзадачи Информация о проверке
0примеры из условияполная
17$$$k_1 = n + m$$$полная
26$$$k_t = 1$$$ для всех $$$t$$$первая ошибка
310 ходы компьютера случайны и равновероятны 0первая ошибка
414 $$$(i_t, j_t)$$$ и $$$(i_{t+1}, j_{t+1})$$$ имеют общую сторону для всех $$$t$$$ 0первая ошибка
511$$$k_t \le 2$$$ для всех $$$t$$$2первая ошибка
617$$$n = 1$$$полная
79$$$n, m \le 40$$$0первая ошибка
89$$$r = c = 1$$$полная
917без дополнительных ограничений0 – 8первая ошибка

Примеры

Входные данные
2 2 1 1
0
1 1 1
2 2 1
3 2 2
4 1 2
Выходные данные
2
Входные данные
3 3 2 2
0
1 2 2
1 1 2
1 1 1
1 2 1
1 3 1
1 3 2
1 3 3
1 2 3
1 1 3
Выходные данные
9

Примечание

В первом примере можно, например, первым ходом передвинуть фишку из $$$(1, 1)$$$ в $$$(1, 2)$$$, а вторым — из $$$(1, 2)$$$ в $$$(2, 2)$$$ и затем в $$$(2, 1)$$$, тем самым поместив ее на удаляемую клетку.