Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

E. Бесконечная карточная игра
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Монокарп и Бикарп играют в карточную игру. Каждая карта имеет два параметра: значение атаки и значение защиты. Карта $$$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$$$.

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

Для каждого набора входных данных выведите три целых числа:

  • количество начальных ходов Монокарпа, которые приводят к победе Монокарпа;
  • количество начальных ходов Монокарпа, которые приводят к ничьей;
  • количество начальных ходов Монокарпа, которые приводят к победе Бикарпа.
Пример
Входные данные
3
3
8 7 4
7 1 10
2
8 4
5 10
9
8 8 5 5 5 4 4 1 4
2 7 5 2 8 9 7 1 9
10
9 8 7 6 5 5 4 3 2 1
7 1 6 7 5 8 8 4 9 6
1
10
5
1
10
5
Выходные данные
1 1 1
2 4 3
0 1 0