Alice and Bob are playing a game. Initially, there is a multiset of strings $S$. Alice and Bob take turns, with Alice going first. In each turn, a player chooses a string $s$ from $S$, removes it from $S$, chooses a character $c$ that appears in $s$, removes all occurrences of $c$ from $s$, and splits $s$ into several substrings at the positions where $c$ was removed. All non-empty substrings resulting from this split are then added to the set $S$. The player who cannot make a move loses.

You are given a tree with $n$ nodes, where each node has a character. Let $\text{path}(u,v)$ denote the string formed by concatenating the characters on the nodes along the shortest path from node $u$ to $v$ (inclusive). There are $q$ queries. For each query, given $u$ and $v$, determine the winner when $S = \{\text{path}(u,v)\}$. If Alice wins, also output the number of possible first moves.

Input

The first line contains two positive integers $n$ and $q$.

The second line contains a string $s$ of length $n$, where the $i$-th character $s_i$ represents the character on node $i$.

The next $n-1$ lines each contain two positive integers $u$ and $v$, describing an edge in the tree.

The next $q$ lines each contain two positive integers $u$ and $v$, representing a query.

Output

Output $q$ lines. For each query, if Alice wins, output Alice followed by the number of possible first moves, separated by a space. Otherwise, output Bob.

Examples

Input 1

10 10
1412002124
1 2
2 3
3 4
4 5
4 6
5 7
5 8
6 9
7 10
7 6
10 2
8 8
7 2
2 9
1 7
5 1
3 8
1 2
7 1

Output 1

Alice 2
Alice 1
Alice 1
Alice 1
Alice 1
Bob
Alice 1
Alice 1
Bob
Bob

Constraints

It is guaranteed that for all test cases: $1 \le n \le 5 \times 10^4$, $1 \le q \le 10^5$, $0 \le s_i < 10$.

Special Property $A$: The tree is guaranteed to be a line.