D. The Marble Duel
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In one of the Squid Game challenges, Seong Gi-hun (Player 456) and Oh Il-nam (Player 001) face off in a game where they start with $$$n$$$ bags of marbles. Each bag has $$$a_{i}$$$ marbles. The rules are simple:

  • On each player's turn, they can choose any bag among the n ones.
  • They can remove exactly 1, x, or y marbles from that bag.
  • The game continues in turns until one player cannot make a valid move.
  • The player who cannot make a valid move loses.
Your task is to determine who will win the game, assuming both players play optimally. The game starts with Seong Gi-hun (Player 456) taking the first turn.
Input

In the first line, there is a single integer $$$t$$$ ($$$1 \leq t \leq 2.10^5$$$), representing the number of testcases.

In each testcase, there are three lines:

  • In the first line, there is a single integer $$$n$$$ ($$$1 \leq n \leq 2.10^5$$$), representing the number of bags of marbles.
  • In the second line, there are two integers $$$x$$$ and $$$y$$$ ($$$3 \leq x \lt y \leq 10^{18}$$$), representing the number of marbles each player can remove.
  • In the third line, there are $$$n$$$ integers $$$a_1,a_2,...,a_n$$$ ($$$1 \leq a_i \leq 10^{18}$$$), representing the number of marbles each bag has.
It's guaranteed that $$$x$$$ is odd and the sum of $$$n$$$ over all testcases is less than $$$2.10^{5}$$$
Output

Output "456" if Seong Gi-hun will win the game, or "001" if Oh Il-nam will win, assuming both players play optimally.

Example
Input
4
1
3 4
2
1
3 4
4
2
3 4
1000000000000000000 1000000000000000000
2
3 4
2 4
Output
001
456
001
456