Problem Statement

Takahashi manages the power supply system of a certain region. This region has N factories and K power plants, which are connected by transmission lines forming a power transmission network.

The locations are numbered from 1 to N + K, where locations 1 through N correspond to factories, and locations N + 1 through N + K correspond to power plants. Specifically, factory i (1 \leq i \leq N) is located at location i, and power plant k (1 \leq k \leq K) is located at location N + k.

The transmission network consists of N + K locations connected by M transmission lines. Each transmission line j (1 \leq j \leq M) bidirectionally connects location U_j and location V_j, and can transmit up to C_j megawatts of power per day. Specifically, letting f_j megawatts denote the amount of power flowing through transmission line j in the direction from location U_j to location V_j, the constraint -C_j \leq f_j \leq C_j must be satisfied. Here, f_j > 0 means power is transmitted from location U_j to location V_j, and f_j < 0 means power is transmitted from location V_j to location U_j.

Each power plant k (1 \leq k \leq K), while operational, can supply any amount of power between 0 and W_k megawatts per day. Each factory i (1 \leq i \leq N) needs to receive at least B_i megawatts of power per day to operate. A factory may receive more than B_i megawatts of power; it operates without issues even if surplus power flows in.

At each location, flow conservation must hold for the power balance. The net inflow \mathrm{net}(v) at location v is defined as follows:

\mathrm{net}(v) = \sum_{\substack{j :\, V_j = v}} f_j - \sum_{\substack{j :\, U_j = v}} f_j

To clarify the meaning of this formula: for transmission line j, when f_j > 0, power flows from U_j to V_j, so f_j flows into location V_j and f_j flows out of location U_j. When f_j < 0, the reverse holds. \mathrm{net}(v) equals the total inflow to location v minus the total outflow from location v, summed over all transmission lines connected to location v.

The following conditions must be satisfied at each location:

• If location v is factory i: \mathrm{net}(v) \geq B_i. That is, a net inflow of at least B_i megawatts must flow into factory i through the transmission lines.
• If location v is an operational power plant k: -W_k \leq \mathrm{net}(v) \leq 0. That is, power plant k can supply between 0 and W_k megawatts of power. Since the supplied power leaves the location, the net inflow is non-positive.
• If location v is a non-operational power plant: \mathrm{net}(v) = 0. It cannot supply power, but as long as inflow equals outflow, it can still function as a relay point through which power passes via transmission lines.

Initially, all K power plants are operational, but it is not guaranteed that all factories can secure the necessary power even in the initial state.

However, due to aging, power plants are expected to fail and shut down sequentially. Specifically, Q events occur in order. At each event t (1 \leq t \leq Q), power plant S_t fails and becomes non-operational. Once a power plant fails, it remains non-operational permanently. Note that Q \leq K, and not all power plants necessarily fail.

For the state immediately after each event occurs, determine whether all factories can secure the necessary power and continue operating. That is, after each event, answer whether there exists a way to route power such that, using only the currently operational power plants, the flow conservation conditions are satisfied and at least B_i megawatts of power is delivered to each factory i.

Constraints

• 1 \leq N \leq 32
• 1 \leq K \leq 32
• 0 \leq M \leq 300
• 1 \leq B_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq W_k \leq 10^9 (1 \leq k \leq K)
• 1 \leq U_j < V_j \leq N + K (1 \leq j \leq M)
• 1 \leq C_j \leq 10^9 (1 \leq j \leq M)
• There is at most one transmission line between any pair of locations (no multi-edges exist)
• 1 \leq Q \leq K
• 1 \leq S_t \leq K (1 \leq t \leq Q)
• S_1, S_2, \ldots, S_Q are all distinct (no power plant fails more than once)
• All input values are integers

Sample Input 1

2 2 3
2 3
2 5
1 3 2
1 4 2
2 4 3
2
1
2

Sample Output 1

Yes
No

Sample Input 2

2 2 3
3 3
6 6
1 2 2
1 3 6
2 4 3
1
2

Sample Output 2

No

Sample Input 3

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

Sample Output 3

Yes
No
No

Sample Input 4

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

Sample Output 4

Yes
Yes
No
No

Sample Input 5

1 1 0
1
1
1
1

Sample Output 5

No