На клетчатой доске размером $$$n \times m$$$, состоящей из $$$n$$$ строк и $$$m$$$ столбцов, в клетке $$$(r, c)$$$, то есть на пересечении $$$r$$$-й сверху строки и $$$c$$$-го слева столбца, расположена фишка. На этой доске вам предстоит сыграть против компьютера в игру, в которой можно перемещать фишку и удалять клетки поля.
Каждый ход устроен следующим образом.
Если компьютер удаляет клетку, на которой находится фишка, игра заканчивается вашей победой. Ваша цель — победить как можно раньше. При этом вы не сообщаете компьютеру свои перемещения, поэтому можете играть нечестно: вместо реального перемещения фишки по полю вы можете следить за всеми возможными ее положениями. Иными словами, если в какой-то момент при удалении клетки $$$(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 | – | примеры из условия | полная | |
1 | 7 | $$$k_1 = n + m$$$ | полная | |
2 | 6 | $$$k_t = 1$$$ для всех $$$t$$$ | первая ошибка | |
3 | 10 | ходы компьютера случайны и равновероятны | 0 | первая ошибка |
4 | 14 | $$$(i_t, j_t)$$$ и $$$(i_{t+1}, j_{t+1})$$$ имеют общую сторону для всех $$$t$$$ | 0 | первая ошибка |
5 | 11 | $$$k_t \le 2$$$ для всех $$$t$$$ | 2 | первая ошибка |
6 | 17 | $$$n = 1$$$ | полная | |
7 | 9 | $$$n, m \le 40$$$ | 0 | первая ошибка |
8 | 9 | $$$r = c = 1$$$ | полная | |
9 | 17 | без дополнительных ограничений | 0 – 8 | первая ошибка |
2 2 1 101 1 12 2 13 2 24 1 2
2
3 3 2 201 2 21 1 21 1 11 2 11 3 11 3 21 3 31 2 31 1 3
9
В первом примере можно, например, первым ходом передвинуть фишку из $$$(1, 1)$$$ в $$$(1, 2)$$$, а вторым — из $$$(1, 2)$$$ в $$$(2, 2)$$$ и затем в $$$(2, 1)$$$, тем самым поместив ее на удаляемую клетку.