Server Queries

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Zenyk does not understand why the External Independent Evaluation (EIE) in computer science has not been introduced yet. He sincerely hopes that it will be introduced next year. Therefore, Zenyk decided to start preparing right now. His uncle Serhiy works at the Ministry of Education and Science of Ukraine and shared the draft EIE computer science curriculum with the young man.

One of the topics was "Computer Networks". Zenyk is well-versed in it. He can say with confidence that HTTP is an application-layer network protocol, and TCP is a transport-layer one. You probably know this too. No?! Don’t know? Well... Don’t worry, I didn’t know either until Zenyk told me.

Zenyk considers a network consisting of \(n\) servers, numbered from 1 to \(n\). These servers are owned by \(m\) IT companies, numbered from 1 to \(m\). The \(i\)-th server in the network belongs to company \(c_i\).

The network has a tree topology. This means that \(n-1\) pairs of servers are connected directly, and also that each server has a connection to any other, possibly through other servers.

One server can send requests to another. Forwarding a request between directly connected servers takes one unit of time. A server that has received a request can forward it to a neighboring server. If a request needs to be sent between servers that do not have a direct connection, then the forwarding takes place along the shortest path in the tree.

Zenyk wants to check if you know computer networks as well as he does. To do this, he asks you \(q\) questions of the form "can the \(x_i\)-th company send a request to the \(y_i\)-th server in no more than \(t_i\) units of time?". If a company wants to send a request, it chooses one of its servers and sends the request from it. If server \(y_i\) belongs to company \(x_i\), we assume that the forwarding time is zero.

Show that you are ready to take the EIE in computer science right now. Answer Zenyk’s questions.

Input

The first line contains two integers \(n\) and \(m\) — the number of servers in the network and the IT companies that own them, respectively.

The second line contains \(n\) integers \(c_i\) — the number of the company that owns the \(i\)-th server.

Each of the next \(n-1\) lines contains two integers \(u_i\) and \(v_i\) — the numbers of servers that have a direct connection.

The next line contains an integer \(q\) — the number of Zenyk’s questions.

The following \(q\) lines contain three integers each \(x_i\), \(y_i\), \(t_i\) — the number of the company that wants to send the request, the number of the server where it needs to be sent, and the number of time units in which this must be done.

Output

In a single line for each query, output 1 if the company can send the request within the time limit, and 0 otherwise.

Constraints

\(1 \le n \le 2 \cdot 10^4\),

\(1 \le c_i, x_i \le m \le 5\),

\(1 \le q \le 10^5\),

\(1 \le u_i, v_i, y_i \le n\),

\(0 \le t_i \le n - 1\),

each company owns at least one server,

for 10 tests, additional constraints are satisfied:

\(1 \le n, q \le 10^3\).

Samples

Input (stdin) сopy	Output (stdout) сopy
7 4 2 1 2 1 3 4 4 1 5 3 6 3 4 5 7 2 1 1 4 7 1 2 0 3 4 1 3 4 1 2 6 0 4 4 2 2 1 1 1 7 3	1000111

Notes

In the example, company 1 owns servers 2 and 4, company 2 — servers 1 and 3, company 3 — server 5, company 4 — servers 6 and 7.