Монокарп и Бикарп играют в карточную игру. Каждая карта имеет два параметра: значение атаки и значение защиты. Карта $$$s$$$ бьет карту $$$t$$$, если значение атаки карты $$$s$$$ строго больше значения защиты карты $$$t$$$.
У Монокарпа есть $$$n$$$ карт, $$$i$$$-я из которых имеет значение атаки $$$\mathit{ax}_i$$$ и значение защиты $$$\mathit{ay}_i$$$. У Бикарпа есть $$$m$$$ карт, $$$j$$$-я из которых имеет значение атаки $$$\mathit{bx}_j$$$ и значение защиты $$$\mathit{by}_j$$$.
На первом ходе Монокарп выбирает одну из своих карт и кладет ее на стол. Бикарп должен побить эту карту своей картой. Затем Монокарп должен побить карту Бикарпа. Затем ход переходит к Бикарпу, и так далее.
После того, как карта побита, она возвращается в руку игрока, который ее сыграл. Это подразумевает, что у игрока, который сейчас ходит, всегда на руках те же карты, что и в начале игры. Игра заканчивается, когда у текущего игрока нет карт, которые побеждают карту, которую только что сыграл его оппонент, и текущий игрок проигрывает.
Если игра длится $$$100^{500}$$$ ходов, объявляется ничья.
И Монокарп, и Бикарп играют оптимально. То есть, если у игрока есть выигрышная стратегия независимо от ходов его оппонента, он играет на победу. В противном случае, если у него есть стратегия для ничьи, он играет на ничью.
Вам нужно вычислить три значения:
Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
Первая строка каждого набора содержит целое число $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — количество карт у Монокарпа.
Вторая строка содержит $$$n$$$ целых чисел $$$\mathit{ax}_1, \mathit{ax}_2, \dots, \mathit{ax}_n$$$ ($$$1 \le \mathit{ax}_i \le 10^6$$$) — значения атаки карт Монокарпа.
Третья строка содержит $$$n$$$ целых чисел $$$\mathit{ay}_1, \mathit{ay}_2, \dots, \mathit{ay}_n$$$ ($$$1 \le \mathit{ay}_i \le 10^6$$$) — значения защиты карт Монокарпа.
Четвертая строка содержит одно целое число $$$m$$$ ($$$1 \le m \le 3 \cdot 10^5$$$) — количество карт у Бикарпа.
Пятая строка содержит $$$m$$$ целых чисел $$$\mathit{bx}_1, \mathit{bx}_2, \dots, \mathit{bx}_m$$$ ($$$1 \le \mathit{bx}_j \le 10^6$$$) — значения атаки карт Бикарпа.
Шестая строка содержит $$$m$$$ целых чисел $$$\mathit{by}_1, \mathit{by}_2, \dots, \mathit{by}_m$$$ ($$$1 \le \mathit{by}_j \le 10^6$$$) — значения защиты карт Бикарпа.
Дополнительные ограничения на входные данные: сумма $$$n$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^5$$$, сумма $$$m$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^5$$$.
Для каждого набора входных данных выведите три целых числа:
338 7 47 1 1028 45 1098 8 5 5 5 4 4 1 42 7 5 2 8 9 7 1 9109 8 7 6 5 5 4 3 2 17 1 6 7 5 8 8 4 9 611051105
1 1 1 2 4 3 0 1 0
Название |
---|