Alice and Bob are working on a new contraption to make the most of their extended summer vacations. However, they ran into some trouble with the mechanics of their machine, specifically, in the gear trains. The complicated meshing of gears has confused them and they require your help to make it functional.

A gear train is a network of gears that are engaged with each other. Mechanically, two gears are said to be engaged or connected if some segment of their teeth interlocks, so that rotating gear forces the rotation of the other gear. This mechanism forces all gears that are engaged with the latter gear to rotate and this motion propagates throughout the train. This type of network can be described in terms of a graph where each vertex represents a gear and an edge denotes that two gears are engaged. 

There are two types of gears, internal and external. The types of gears depend on which region their teeth are present. Note that all gears are fixed to their position.

For example, the first network can be described as a graph with \(5\) nodes (all gears are external) and \(5\) undirected edges \((1,2), (1,3), (2,4), (3,4), (4,5)\). If we rotate gear \(1\) in clockwise direction, then gears \(2\) and \(3\) rotate in anticlockwise direction, gear \(4\) rotates in clockwise direction, and gear \(5\) rotates in anticlockwise direction.

The second network can be described as a graph with \(6\) nodes (gear \(6\) is internal and all other gears are external) and \(8\) edges. If you rotate gear \(1\) in clockwise direction, then gears \(2,3,4,5\) rotate in anticlockwise direction and gear \(6\) also rotates in anticlockwise direction.

To test their system, Alice grabs one gear, Bob grabs another (not necessarily different) gear and both of them try to rotate their gear in some direction simultaneously.

In the first example, if you try to simultaneously rotate gears \(1\) and \(5\) in clockwise direction, none of the gears rotate because the gears are made to move in opposite directions by the two forces. However, if gear \(1\) is rotated in clockwise direction and gear \(5\) is rotated in anticlockwise direction, then all gears can rotate in the same way as the provided example.

A rotation is functional if and only if no gear is forced to rotate in opposite directions (directly or indirectly).

You are given a network of \(N\) gears and \(M\) connections. Determine whether rotating two given gears in given directions results in a functional rotation. You must answer \(Q\) queries.

Input format

• The first line contains \(3\) integers \(N,\ M,\ Q\) \((1\leq N,Q\leq10^5 , 0\leq M\leq 10^5)\) denoting the number of gears, the number of connections and the number of queries respectively.
• The second line contains \(N\) integers the \(i^{th}\) of which is \(1\) if the gear is external or \(-1\) if it is internal.
• The next \(M\) lines contain two integers \(u\) and \(v\) \((1\leq u,v \leq N)\) denoting that gears \(u\) and \(v\) are engaged.
• The next \(Q\) lines contain \(4\) integers \(g_p,\ g_f,\ dir_p,\ dir_f\) \((1\leq g_p,g_f \leq N)\) \((dir_p,dir_f \in \{-1,1\})\) denoting the gears held by Alice and Bob and the directions in which they are rotated.

Note

• It is guaranteed that the graph does not contain self-loops or parallel edges.
• It is guaranteed that no two internal gears are engaged with each other.

Output format

For each query, print a single line containing 'YES' if the rotation is functional or 'NO' if it is not.