Background

Time limit 3 s, memory 128 MB.

I feel I am going to fail the NOI Qualifier.

Scum's Wish is an interesting anime.

The cute Hanabi likes her onii-chan Narumi, who has chatted and joked with her since childhood. Onii-chan really wants to be a teacher, and as the plot goes, he becomes Hanabi’s homeroom teacher.

However, someone strange named Akane Minagawa steals onii-chan away!

Hanabi feels very down, and then she sees someone named Mugi also feeling down. It turns out Mugi likes Teacher Akane.

From then on, Hanabi and Mugi chat and joke every day and decide to be together, treating each other as substitutes for the people they actually like.

Because Hanabi is very cute, many strange people like her, such as a girl named Sanae Ebato.

Because Mugi also looks good, many strange people like him, such as a girl named Most Kawaii.

And then their cheerful life begins.

If you haven’t watched this anime, you can ignore the above.

Following the usual trope, now onii-chan would ask Hanabi an OI problem (usually data structures). Hanabi definitely doesn’t do OI, so she comes to ask you, an IOI Au contestant, and you will surely help her.

But this trope is too boring, so let’s change it (without changing the fact that you are an IOI Au contestant).

One day Hanabi watched a few interesting anime called “Is It Wrong to Look for Crossdressing on W??,” “Starting from Crossdressing, ?X?,” and “My Big Boss Can’t Possibly Be This Cute,” and then discovered ??H is amazing. She then traveled to another world and bantered with ???.

Hanabi made a deal with ???: Hanabi helps ??? solve a problem, and ??? helps Hanabi rewrite the program of Earth Online so Hanabi and onii-chan can be together.

Although ??? is very powerful, he doesn’t know data structure problems. He recently encountered an interesting data structure problem, so he accepted the deal.

But Hanabi also doesn’t know data structure problems.

So we’re back to the old trope—she relies on you, the IOI Au contestant, to help her!

If you haven’t watched these anime, you can still ignore the above.

Here is a classic diagram to explain this relationship (it’s actually not that silly).

Problem 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