Hoshizora Rin is a particularly active girl.
One day, Rin arrived in a distant city. This city has $N$ buildings, numbered from $1$ to $N$, where the city center is numbered $1$. The city has $M$ two-way streets, each connecting two buildings. Some of these streets are connected end-to-end to form cycles.
Through long-term visits, Rin has identified two characteristics of this city: 1. All buildings can be reached from the city center. 2. Any street belongs to at most one simple cycle.
What makes Rin ecstatic is that every building sells ramen. There are many different types of ramen, but for Rin, they only differ in their "greasiness level." Therefore, we consider ramen with the same greasiness level to be the same type. Since the greasiness level of ramen may differ between buildings, we use a positive integer to represent the greasiness level.
Ramen is Rin's favorite, but now it is the evening rush hour, and the city's traffic has become very congested. Rin can only travel through streets that are not blocked to taste the ramen at the buildings she can reach.
Now, Rin wants to know: if she is currently at building $x$, and all streets on all simple paths from the city center to $x$ are blocked, then among the ramen she can taste (note that ramen types that do not appear cannot be counted): 1. How many types of ramen have a greasiness level $\le y$ and have been tasted an odd number of times? 2. How many types of ramen have a greasiness level $\le y$ and have been tasted an even number of times?
Input
The first line contains two positive integers $N, M$, with meanings as described above.
The second line contains $N$ positive integers, where the $i$-th number $A_i$ represents the greasiness level of the ramen sold at the $i$-th building.
The next $M$ lines each contain two positive integers $x, y$, representing a two-way street between buildings $x$ and $y$. The data guarantees $1 \le x < y \le N$.
The next line contains a positive integer $Q$, representing the number of queries.
The next $Q$ lines each contain three non-negative integers $ty, x, y$, where $x$ is the building number, $y$ is the limit on the greasiness level, $ty = 0$ represents a query for even counts, and $ty = 1$ represents a query for odd counts.
Output
A total of $Q$ lines, each containing the answer for the corresponding query.
Examples
Input 1
5 6 2 1 6 7 7 1 2 1 3 2 4 4 5 4 5 1 3 3 0 3 2 0 3 1 0 1 7
Output 1
0 0 1
Note
Building $3$ can only reach itself, while building $1$ can reach all buildings.
Constraints
Hint: Please pay attention to the $\le$ in the data range. The $y$ mentioned in the special conditions refers to the $y$ in the queries. For $100\%$ of the data, $y \le 10^6$.
| ID | $N$ | $M$ | $Q$ | $A_i$ | Special Conditions |
|---|---|---|---|---|---|
| 0 | $10$ | $\le 15$ | $10$ | $\le 10$ | |
| 1 | $100$ | $\le 150$ | $100$ | $\le 10$ | None |
| 2 | $1000$ | $\le 1500$ | $1000$ | $\le 100$ | |
| 3 | $1000$ | $\le 1500$ | $1000$ | $\le 100$ | |
| 4 | $80000$ | $79999$ | $50000$ | $\le 1000$ | $y$ in queries is a non-negative power of $10$ |
| 5 | $80000$ | $79999$ | $50000$ | $\le 1000$ | |
| 6 | $80000$ | $\le 120000$ | $50000$ | $\le 1000$ | |
| 7 | $80000$ | $\le 120000$ | $50000$ | $\le 1000$ | |
| 8 | $80000$ | $79999$ | $50000$ | $\le 10^6$ | All $ty = 0$ |
| 9 | $80000$ | $79999$ | $50000$ | $\le 10^6$ | All $ty = 1$ |
| 10 | $80000$ | $\le 120000$ | $50000$ | $\le 10^6$ | All $ty = 0$ |
| 11 | $80000$ | $\le 120000$ | $50000$ | $\le 10^6$ | All $ty = 1$ |
| 12 | $80000$ | $\le 120000$ | $80000$ | $\le 10^6$ | All $ty = 1$ and $y = 10^6$ |
| 13 | $80000$ | $\le 120000$ | $80000$ | $\le 10^6$ | |
| 14 | $90000$ | $\le 150000$ | $90000$ | $\le 10^6$ | None |
| 15 | $90000$ | $\le 150000$ | $90000$ | $\le 10^6$ | |
| 16 | $100000$ | $\le 150000$ | $100000$ | $\le 10^6$ | None |
| 17 | $100000$ | $\le 150000$ | $100000$ | $\le 10^6$ | |
| 18 | $100000$ | $\le 150000$ | $100000$ | $\le 10^6$ | |
| 19 | $100000$ | $\le 150000$ | $100000$ | $\le 10^6$ |