Description

The problem is as follows:

You are given a sequence $a$ of length $n$, with $m$ operations. Each operation asks whether, in a given interval, you can choose two numbers whose difference equals $x$, or two numbers whose sum equals $x$, or two numbers whose product equals $x$. These three operations correspond to operations $1, 2, 3$, respectively.

The two chosen numbers may come from the same position.

Input Format

The first line contains two numbers $n, m$.

The second line contains $n$ numbers representing $a_i$.

Each of the next $m$ lines contains four numbers opt l r x.

$opt$ indicates which operation it is, $l, r$ specify the interval, and $x$ is the value for this operation.

Output Format

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

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

bi
bi
bi
bi
bi
bi
bi
bi
bi
bi

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

hana
bi
hana
hana
bi

Hint

Define $c$ as the maximum of each $x$ and all $a_i$. Assume $a_i \geq 0$ and each $x \geq 0$.

For $10\%$ of the testdata, $n, m, c \leq 100$.

For another $10\%$ of the testdata, $n, m, c \leq 3 \times 10^3$.

For another $10\%$ of the testdata, only operation $1$ appears.

For another $10\%$ of the testdata, only operation $2$ appears.

For another $10\%$ of the testdata, only operation $3$ appears.

For $100\%$ of the testdata, $n, m, c \leq 10^5$.

Translated by ChatGPT 5