Капитан математического патруля понял, что стрелять в Бернарда бесполезно и пошел врукопашную. Бернард не собирается сдаваться без боя.
Бернард знает $$$N$$$ приемов, каждый из которых является совокупностью двух одновременно происходящих действий, верхнего и нижнего. Есть три вида действия: $$$0$$$ — ожидание, $$$1$$$ — удар, $$$2$$$ — блок. Например, верхний удар означает удар в верхнюю часть тела противника, нижний блок означает защиту от нижнего удара противника. Кроме того, у каждого действия есть время исполнения $$$T$$$. В случае удара это означает, что удар достигнет цели через $$$T$$$ миллисекунд. В случае блока это означает, что любой удар в этом направлении, который произойдет после $$$T$$$-й миллисекунды, будет заблокирован. Для ожидания время не имеет значения. Все значения $$$T$$$ среди всех приемов и Бернарда, и его противника различны.
Когда удар попадает в противника, его прием прерывается. Это означает, что если оба оппонента могут ударить друг друга, побеждает тот, чей удар попал по противнику первым. Если после применения приемов все удары были заблокированы, будет ничья.
Капитан патруля знает $$$M$$$ приемов, работающих по тем же правилам. Бернард и его противник применяют один свой прием, причем капитан может применить любой прием с одинаковой вероятностью. Помогите Бернарду выбрать свой прием так, чтобы вероятность победы была наибольшей. Если таких приемов несколько, выберите среди них тот, у которого больше вероятность ничьей. Если и таких приемов несколько, выберите среди них прием с минимальным номером.
Первая строка содержит два целых числа $$$N$$$ и $$$M$$$ $$$(2 \le M \le N \le 1000)$$$ — количество приемов Бернарда и его противника.
Следующие $$$N$$$ строк содержат по четыре целых числа $$$A$$$, $$$B$$$, $$$C$$$, $$$D$$$ $$$(0 \leq A, C \leq 2)$$$, $$$(1 \leq B, D \leq 10^6)$$$ — описание приемов Бернарда: номер верхнего действия, время верхнего действия, номер нижнего действия и время нижнего действия.
Следующие $$$M$$$ строк содержат по четыре целых числа $$$A$$$, $$$B$$$, $$$C$$$, $$$D$$$ $$$(0 \leq A, C \leq 2)$$$, $$$(1 \leq B, D \leq 10^6)$$$ — описание приемов капитана: номер верхнего действия, время верхнего действия, номер нижнего действия и время нижнего действия. Все значения $$$B$$$ и $$$D$$$ среди всех приемов и Бернарда и его противника различны.
Выведите единственное целое число — порядковый номер лучшего приема.
| Группа | Доп. ограничения | Баллы | Требуемые подзадачи | Тип проверки |
| $$$1$$$ | — | $$$100$$$ | — | Полная |
3 3 1 5 2 3 0 15 1 6 2 7 2 8 2 1 1 10 2 2 2 9 1 12 2 4
2
3 3 0 14 1 4 2 7 0 12 2 5 1 6 2 1 1 10 2 2 2 9 1 8 2 3
3
2 2 1 4 2 8 1 5 1 7 2 1 2 3 1 10 1 11
1
В первом тесте первый прием Бернарда против первого приема капитана приводит к ничье, т.к. капитан ставит верхний блок на 1-й миллисекунде, блокируя верхний удар на 5-й миллисекунде. В это время Бернард ставит нижний блок на 3-й миллисекунде, блокируя нижний удар капитана на 10-й миллисекунде. Первый прием Бернарда против второго приема оппонента также ничья. При этом первый прием Бернарда побеждает третий прием оппонента, потому что верхний удар на 5-й миллисекунде попадает раньше, чем удар противника на 12-й. Второй прием Бернарда побеждает первый и второй прием противника, но проигрывает третьему. Третий прием Бернарда имеет ничью со всеми приемами оппонента.
| Name |
|---|