The kapok trees in her old home still grow in Little N's gradually fading memories. Her memories of her old home can be represented by a sequence $[a_0, a_1, \ldots, a_{n-1}]$ of length $n$.

Each kapok tree in her old home is shaped like an unrooted tree with labeled vertices. Little N's impression of a kapok tree can be described by an interval $[l, r)$ of her memory sequence:

• The tree has $k = r - l + 2$ vertices, numbered from $0$ to $k - 1$.
• $[\min(a_l, k - 1), \min(a_{l+1}, k - 1), \ldots, \min(a_{r-1}, k - 1)]$ is its Prüfer sequence. The definition of a Prüfer sequence is given in the Hints section.

While recalling the past, Little N also asks you $m$ queries. The $i$-th query ($0 \le i < m$) is:

• Are vertices $x_i$ and $y_i$ adjacent in the kapok tree corresponding to the interval $[l_i, r_i)$ of her memory sequence?

Implementation Details

You do not need to, and must not, implement the main function.

Make sure that your submitted source file includes the header kapok.h by placing the following code at the beginning of your program:

#include "kapok.h"

Implement the following function in the submitted source file kapok.cpp:

std::vector<bool> kapok(int c, int n, int m,
  std::vector<int> a, std::vector<int> l, std::vector<int>
  r, std::vector<int> x, std::vector<int> y);

• $c$, $n$, and $m$ are the test-case number, the length of the memory sequence, and the number of queries, respectively. $c = 0$ indicates that the test case is an example.
• $a$ is the memory sequence.
• $l$ and $r$ give the two endpoints of the interval specified in each query.
• $x$ and $y$ give the labels of the two vertices specified in each query.
• This function must return a sequence $f_0, f_1, \ldots, f_{m-1}$ of length exactly $m$, where $f_i$ ($0 \le i < m$) is the result of the $i$-th query.
• For each test case, the grader calls this function exactly once.

The problem directory contains example code in template_kapok.cpp, which you may consult when writing your own implementation.

Testing Your Program

Use the following command in the problem directory to compile an executable:

g++ grader.cpp kapok.cpp -o kapok -O2 -std=c++14 -static

The compiled executable kapok behaves as follows:

• It reads data from standard input in the following format:

  • The first line contains three nonnegative integers $c, n, m$.
  • The second line contains $n$ nonnegative integers $a_0, a_1, \ldots, a_{n-1}$.
  • Line $i + 3$ ($0 \le i < m$) contains four nonnegative integers $l_i, r_i, x_i, y_i$.

• It writes data to standard output in the following format:

  • Line $i + 1$ ($0 \le i < m$) contains one nonnegative integer: $0$ means that $f_i$ is false, and $1$ means that $f_i$ is true.

Examples

Input 1

0 8 3
2 0 2 6 0 7 2 2
0 3 0 2
3 5 1 2
0 0 0 1

Output 1

1
0
1

Note

• The tree corresponding to $[0, 3)$ has $5$ vertices, Prüfer sequence $[2, 0, 2]$, and edge set $\{(1, 2), (0, 3), (0, 2), (2, 4)\}$. Thus, vertices $0$ and $2$ are adjacent.
• The tree corresponding to $[3, 5)$ has $4$ vertices, Prüfer sequence $[3, 0]$, and edge set $\{(1, 3), (0, 2), (0, 3)\}$. Thus, vertices $1$ and $2$ are not adjacent.
• The tree corresponding to $[0, 0)$ has $2$ vertices and an empty Prüfer sequence. Its only edge is $(0, 1)$, so vertices $0$ and $1$ are adjacent.

Example 2

See kapok/kapok2.in and kapok/kapok2.ans in the contestant directory.

This example satisfies the constraints for test cases $3$ through $5$.

Example 3

See kapok/kapok3.in and kapok/kapok3.ans in the contestant directory.

This example satisfies the constraints for test cases $3$ through $5$.

Constraints

All test data satisfy:

• $1 \le n, m \le 2 \times 10^5$;
• $0 \le a_i < n + 2$ for every $0 \le i < n$;
• $0 \le l_i \le r_i \le n$ and $0 \le x_i, y_i < r_i - l_i + 2$ for every $0 \le i < m$.

• Special property A: For every $0 \le i < m$, after $l_i$ and $r_i$ are given, the ordered pair $(x_i, y_i)$ is generated independently and uniformly at random from all ordered pairs satisfying the constraints.

Hints

For an unrooted tree $T$ whose vertices are numbered from $0$ to $c - 1$ ($c \ge 2$):

• Perform $c - 2$ operations in order. The $i$-th operation ($0 \le i < c - 2$) is as follows:

  • Find the leaf $v_i$ with the smallest current label.
  • Record the label $p_i$ of its only neighbor.
  • Then remove $v_i$ and its only incident edge from $T$.

• The resulting sequence $[p_0, p_1, \ldots, p_{c-3}]$ of length $c - 2$ is the Prüfer sequence of $T$.