Description

Brahc and Winlere are playing a game with a binary string. Brahc moves first. On each turn:

• Brahc may delete any even-length substring consisting of identical characters.
• Winlere may delete any odd-length substring consisting of identical characters.

When deleting a substring, its left side and right side will merge together. The whole string will not split.

The player who cannot make a move loses.

Before each round starts, they will take the binary string from the previous round's game and choose one contiguous segment to flip all bits in it (turning $\texttt{0}$ into $\texttt{1}$ and $\texttt{1}$ into $\texttt{0}$).

Given that both Brahc and Winlere play optimally, determine the winner for each round.

Format

Input

The first line contains two integers $n,q\,(1\leq n\leq2\times10^5, 1\leq q\leq 10^6)$, the length of the binary string and the number of rounds.

The second line contains $n$ numbers, each number is either $0$ or $1$, representing the initial binary string.

The next $q$ lines, each containing two integers $l,r\,(1\leq l\leq r\leq n)$, represent the segment to flip in the current round.

Output

$q$ lines, each line contains either $\texttt{Brahc}$ or $\texttt{Winlere}$, representing the winner of the corresponding round.

Samples

6 1
1 0 1 1 0 0
5 6

Winlere