GemNuAi

Jam in eye because you are kinda clumsy. In spite of this, you're a mega chef, and have unreasonably high standards, only cooking with golden knives. This isn't really your story, it's the story of $N$ chefs numbered from $0$ to $N-1$ (sorted by how rare they like their meat cooked). For each such chef, $2$ intervals are known, chef $i$ being represented by the intervals $[A_i, B_i]$ and $[C_i, D_i]$, respectively. These intervals are represented on the culinary axis with values from $1$ to $N$, where each element represents a type of dish. For each chef $i$, it is known that he can prepare any dish in the interval $[A_i, B_i]$, but in the event that he takes part in an international culinary competition (very unlikely), he wishes to prepare for the competition the dishes in the interval $[C_i, D_i]$ (and you know how life is, what you can do isn't always what you want to do).

And boom, an international culinary competition follows (who would have expected it?) called Shawarma Fest — for if it weren't true, it wouldn't be worth mentioning. The chefs started forming teams, and the gossip is in full swing. There are $2$ big criteria for a subset of chefs to be able to form a team:

• They must represent a contiguous interval of indices. For example, the chef with index $3$ can team up with the chef with index $6$ only if chefs $4$ and $5$ also join the team. Not for any other reason, but because chef $3$, who cooks his meat rarer, won't team up with just any old-fashioned chef with index $6$ who cooks his meat more "well done," unless all the other chefs in between are also on the team to mediate the conflict and make sure they don't argue until time runs out.

• In addition, an interval of chefs $[x, y]$ can form a team if, for every chef $i$ in the team and for every dish $j$ in the interval $[C_i, D_i]$, there exists at least one chef $k$ in the team ($k$ can be equal to $i$) who can cook dish $j$.

Requirement

You are given $Q$ queries, each query consisting of two indices $x$ and $y$. For each query, you must determine whether the subsequence $[x, y]$ of chefs can form a team or not.

Depending on how skilled you feel, you may choose to answer these queries offline (requirement $1$) or online (requirement $2$), and you will receive points accordingly.

Implementation Details

You will need to implement several functions. The first of them is:

int precompute(int N, int Q, std::vector<int> A, std::vector<int> B, std::vector<int> C, std::vector<int> D)

which receives as parameters:

• $N$, the total number of chefs
• $Q$, the number of queries
• $A, B, C$ and $D$, vectors with the meaning given in the statement

The precompute function must process the received data and then return a value from the set $\{1, 2\}$ depending on which requirement you choose to solve. Next, you will need to implement one function for each requirement, called cerinta_1 and cerinta_2.

std::vector<bool> cerinta_1(std::vector<std::pair<int, int>> queries)

which:

• receives as a parameter queries, a vector indexed from $0$ containing the $Q$ queries;
• returns a vector of length $Q$ where position $i$ holds the answer to the $i$-th query, for $0 \leq i < N$.

bool cerinta_2(std::pair<int, int> query)

which:

• receives as a parameter query, a pair representing a single query;
• returns true if the answer to the query is positive and false otherwise.

For a test in which the precompute function returned the value:

• $1 \ -$ the cerinta_1 function will be called exactly once;
• $2 \ -$ the cerinta_2 function will be called $Q$ times.

Note that if you always opt for the same requirement, then you are not required to implement a valid solution for both cases, but you must still include a definition of the function. See the template in sample-solution.cpp.

Constraints and Notes

• $1 \leq N \leq 500 \ 000$.
• $1 \leq Q \leq 5 \ 000 \ 000$.
• $1 \leq A_i \leq B_i \leq N$.
• $1 \leq C_i \leq D_i \leq N$.
• $0 \leq L_i \leq R_i < N$.
• Solving requirement $1$ is worth $70\%$ of the test's score.

Example 1

input

10 3
1 3 1 2 1 1 1 1 2 1
3 3 3 2 2 1 2 2 3 3
1 1 2 1 1 1 2 1 2 1
1 3 2 2 1 3 2 1 2 2
2 4
5 7
7 9

output

query 0: 1
query 1: 0
query 2: 1

Explanation

The chefs in the subsequence $[2, 4]$ can together prepare the dishes $\{1, 2, 3\}$, therefore they can be part of the same team.

The chefs in the subsequence $[5, 7]$ cannot together prepare the dishes $\{1, 2\}$, which do not fully cover the interval $[C_5, D_5]$