I. Shift or Remove
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Alice and Bob are playing a game on $$$n$$$ piles of stones, numbered from $$$1$$$ to $$$n$$$. Initially, pile $$$i$$$ contains $$$a_i$$$ stones. Alice moves first.

On each move, the current player performs an operation once or twice. The operations are performed in succession, and each operation must be legal at the moment it is performed.

A single operation can be one of the following:

  • choose an index $$$i$$$ such that pile $$$i$$$ is non-empty, then remove one stone from pile $$$i$$$;
  • choose indices $$$i \lt j$$$ such that pile $$$i$$$ is non-empty, then remove one stone from pile $$$i$$$ and add one stone to pile $$$j$$$.

A player who cannot make a move loses.

Determine who wins if both players play optimally. If Alice wins, output any winning first move for her.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1\le n\le 2\cdot 10^5$$$) — the number of piles.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\le 10^{18}$$$) — the initial sizes of the piles.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output

For each test case:

  • if Bob wins, output a single line containing Bob;
  • otherwise, output a line containing Alice and an integer $$$q$$$ ($$$1\le q\le 2$$$) — the number of operations in Alice's first move. Then output $$$q$$$ more lines describing these operations in the order they are performed.

Each operation must have one of the following forms:

  • 1 i — remove one stone from pile $$$i$$$;
  • 2 i j — remove one stone from pile $$$i$$$ and add one stone to pile $$$j$$$.

All printed operations must be legal when they are performed.

If there are multiple valid answers, output any of them.

Example
Input
5
2
1 2
2
3 3
3
1 1 2
3
1 1 1
2
100000007998244353 6769676967696769
Output
Alice 1
2 1 2
Bob
Alice 2
2 1 3
1 2
Alice 2
2 1 3
2 2 3
Alice 2
1 1
1 2