| Codeforces Round 1117 (Div. 2) |
|---|
| Закончено |
Два гиганта Бо и Бер играют в игру. У каждого гиганта есть своя горная гряда. Вы уже успели измерить все эти горы и теперь знаете, что высоты гор в гряде Бо $$$a_1, a_2, \ldots a_n$$$, а в гряде Бера $$$b_1, b_2, \ldots b_m$$$; горы нумеруются слева направо у Бо и справа налево у Бера. В начале игры гиганты стоят на горе с номером $$$1$$$. Таким образом, они смотрят друг на друга и видят все свои горы и все горы соперника. Оказалось, что Бо и Бер ценители прекрасного, поэтому горы в грядах располагаются в порядке невозрастания, строго говоря, $$$a_i \ge a_{i+1}$$$ для $$$1 \le i \lt n$$$ и $$$b_i \ge b_{i+1}$$$ для $$$1 \le i \lt m$$$.
На рисунке ниже изображен пример начального расположения, где Бо имеет гряду $$$a_1, a_2, a_3 = 3, 2, 1$$$, Бер имеет гряду $$$b_1, b_2 = 4, 2$$$. Для простоты горы изображены прямоугольниками, слева горы Бо, справа Бера. Для Вашего хорошего настроения гиганты Бо и Бер обозначены бобрами.
Бо и Бер не очень умны, поэтому каждый ход они делают одно и то же действие. А именно, гигант в свой ход берёт валун и кидает его в гору, на которой стоит его соперник; от этого действия высота этой горы уменьшается на 1. Если гигант в свой ход видит, что гора прямо перед ним выше (с номером на 1 больше), чем та, на которой он стоит, то он перепрыгивает на неё. Если же гигант в свой ход обнаруживает, что стоит на обычной земле (высота текущей горы 0) и перед ним нет больше гор, то признаёт своё поражение. Первым ходит Бо.
Вы знаете, что их игра может длиться очень долго, ввиду огромных высот гор и их количества, поэтому вы хотите посчитать, кто же победит.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ — количество гор в гряде первого и второго гиганта соответственно ($$$1 \le n, m \le 100$$$).
Вторая строка набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots a_n$$$ — высоты гор первого гиганта ($$$1 \le a_i \le 10^9$$$; $$$a_i \ge a_{i+1}$$$).
Третья строка набора входных данных содержит $$$m$$$ целых чисел $$$b_1, b_2, \ldots b_m$$$ — высоты гор второго гиганта ($$$1 \le b_i \le 10^9$$$; $$$b_i \ge b_{i+1}$$$).
Для каждого набора входных данных выведите единственное число — номер гиганта, который победит.
61 1111 1121 244 14 24 3 2 110 14 24 3 2 16 54 24 3 2 17 5
122212
В первом наборе первым же своим ходом Бо уменьшит высоту единственной горы Бера до $$$0$$$ и победит.
Во втором наборе Бо уменьшит высоту горы Бера до $$$1$$$, а Бер уже следующим своим ходом победит.
В третьем наборе за первые $$$3$$$ раунда высота гор Бо и Бера уменьшится до $$$1$$$. Затем Бо уменьшит высоту горы Бера до $$$0$$$, но у Бера осталась ещё одна гора; в свой ход он перепрыгивает на неё и этим же ходом побеждает, уменьшая высоту единственной горы Бо до $$$0$$$.
