After hewmatt10's one and only friend, astrocat879, left his Art Academy, hewmatt10 had been running all across the city in hopes of finding someone that he can replace. Searching far and wide, he eventually stumbles upon the love of his life: [REDACTED]. Wanting to see whether or not hewmatt10 is worthy, [REDACTED] gives him a seemingly impossible task, defined as such:

You are given an undirected, acyclic graph with $N$ nodes and $M$ edges, such that $M\le N-1$. In other words, you are given a forest of trees. You are also given a special value, called $K$. Each node will be associated with a group $g_i$, where $1\le g_i\le K$.

For each connected component, you may choose to do ONE of the following operations:

Operation	Description
0	Do nothing with this component.
1	Increase every node's group by 1.
2	Multiply every node's group by 2.
3	Take the bitwise XOR of every node's group by 15.

You must perform operations such that the absolute difference between the number of nodes between two groups $x_i$ and $y_i$ is as FAR AWAY as $z_i$ as possible. You will be asked to do this $Q$ times.

hewmatt10, not wanting to risk his only chance, is relying on YOU to help him. However, because you do NOT want to help him, you have decided to do the EXACT OPPOSITE of what he asks - perform operations such that the absolute difference is EQUAL to $z_i$.

Input Specification

The first line will contain the integers $N$, $M$, $K$, and $Q$. $(1\le N\le 3\cdot {10}^2)$, $(0\le M\le N-1)$, $(2\le K\le 15)$, $(1\le Q\le 3\cdot {10}^4)$.

The next line will contain $N$ spaced integers $g_i$ $(1\le g_i\le K)$, representing the group of node $i$ $(1\le i\le N)$.

The next $M$ lines will contain two spaced integers $a_i$ and $b_i$, indicating that nodes $a_i$ and $b_i$ are connected $(1\le a_i,b_i\le N)$.

The next $Q$ lines will contain three spaced integers $x_i$, $y_i$, and $z_i$ $(1\le x_i,y_i\le K)$, $(1\le z_i\le N)$.

Output Specification

For each of the $Q$ questions, output a YES if it is possible to get groups $x_i$ and $y_i$ to have an absolute difference of $z_i$, and a NO otherwise, followed by a newline.

If the answer is YES, this will then be followed by $N$ spaced integers $o_i$, followed by a newline, where $o_i$ corresponds to the type of operation performed on node $i$'s connected component to reach $z_i$. If there are multiple such ways to perform operations, print the arrangement that is lexicographically least.

Clarification: Arrangement refers to the $N$ spaced integers on the second line.

Constraints

For this problem, you will NOT be required to pass the sample to receive points. In addition, all subtasks are disjoint, and you are NOT required to pass previous subtasks to earn points for a specific subtask.

Subtask 1 [10%]

$1\le N\le 10$

$K=2$

$Q=1$

Subtask 2 [10%]

$M=N-1$

Subtask 3 [80%]

No additional constraints.

Sample Input

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

Sample Output

YES
0 0 0 0 0 1 0 0 0 1

Explanation

Operation $1$ can be performed on the connected component containing nodes $6$ and $10$. After performing this operation, there will be $7$ nodes with group $3$, and $1$ node with group $1$. This is the lexicographically least way to perform operations such that the absolute difference between groups $1$ and $3$ is equal to $6$.