Problem Description

This problem is as follows:

Given a sequence \(a\) of length \(n\), there are \(m\) operations. Each operation queries whether it is possible to select two numbers within a given interval such that their difference is \(x\), or their sum is \(x\), or their product is \(x\). These operations are respectively labeled as operations \(1, 2, 3\).

The two numbers selected can be from the same position.

Input Format

The first line contains two numbers \(n, m\).

The next line contains \(n\) numbers representing \(a_i\).

The following \(m\) lines each contain four numbers opt l r x.

opt indicates the type of operation, \(l, r\) indicate the interval for the operation, and \(x\) is the \(x\) for this operation.

Output Format

For each query, if it is possible, output hana, otherwise output bi.

Sample Input and Output

Input Sample #1

10 10
1 1 8 9 9 1 1 1 1 9 
3 5 9 42
2 1 3 14
2 3 5 2
2 3 3 6
1 6 10 18
3 4 9 14
2 1 4 22
3 1 3 32
2 5 6 32
3 1 9 17

Output Sample #1

bi
bi
bi
bi
bi
bi
bi
bi
bi
bi

Input Sample #2

5 5
1 1 2 3 4
2 1 1 2
1 1 2 2
3 1 1 1
3 5 5 16
1 2 3 4

Output Sample #2

hana
bi
hana
hana
bi

Notes

Define \(c\) as the maximum value between each \(x\) and \(a_i\), where \(a_i \geq 0\) and each \(x \geq 2\).

For \(10\%\) of the data, \(n, m, c \leq 100\).

For another \(10\%\) of the data, \(n, m, c \leq 3 \times 10^3\).

For another \(10\%\) of the data, only operation \(1\) is present.

For another \(10\%\) of the data, only operation \(2\) is present.

For another \(10\%\) of the data, only operation \(3\) is present.

For \(100\%\) of the data, \(n, m, c \leq 10^5\).

见题面 Input 部分

见题面 Output 部分