M. Glowing Bulbs
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are infinitely many bulbs, numbered $$$1,2,3,\ldots$$$, and a sink numbered $$$0$$$.

Alice and Bob play a game. Alice moves first. On each turn, the player:

  1. chooses a glowing bulb $$$x$$$;
  2. chooses an integer $$$y$$$ such that $$$0\le y \lt x$$$;
  3. turns bulb $$$x$$$ off;
  4. if $$$y \gt 0$$$, toggles bulb $$$y$$$: an off bulb turns on, and a glowing bulb turns off.

If $$$y=0$$$, nothing is toggled. A player who has no glowing bulb to choose loses.

You are given an array $$$a$$$ and $$$q$$$ queries. Each query $$$[l,r]$$$ starts an independent game. At the start of that game, bulb $$$x$$$ is glowing if and only if $$$x$$$ appears at least once in [ a_l,a_{l+1},...,a_r. ] Repeated occurrences of the same value still light only one bulb.

For every query, determine the winner if both players play optimally.

Input

The first line contains an integer $$$t$$$ ($$$1\le t\le 10^4$$$) — the number of test cases.

For each test case:

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1\le n,q\le 2\cdot 10^5$$$) — the array length and the number of queries.

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\le 10^9$$$).

Each of the next $$$q$$$ lines contains two integers $$$l$$$ and $$$r$$$ ($$$1\le l\le r\le n$$$), describing one query.

The sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$. The sum of $$$q$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output

For each query, print Alice if Alice wins; otherwise, print Bob.

Example
Input
1
5 5
1 2 1 3 2
1 1
1 3
1 5
2 4
3 3
Output
Alice
Alice
Bob
Bob
Alice