In an RPG game, the final battle is a duel between the protagonist and a Boss. The scenario is simplified as follows:

The protagonist has a maximum HP of $HP$, a maximum MP of $MP$, and a maximum SP of $SP$. The Boss has an HP with a maximum of $M$.

There are $N$ rounds in total. In each round, the protagonist acts first and can choose one of the following actions:

1. Normal attack: Reduces the Boss's HP by $X$ and increases the protagonist's SP by $DSP$ (up to the maximum).
2. Spell attack: There are $N_1$ types of spells. The $i$-th spell consumes $B_i$ MP and reduces the Boss's HP by $Y_i$ (requires current MP $\ge B_i$).
3. Special skill attack: There are $N_2$ types of special skills. The $i$-th skill consumes $C_i$ SP and reduces the Boss's HP by $Z_i$ (requires current SP $\ge C_i$).
4. Use HP potion: Increases the protagonist's HP by $DHP$ (up to the maximum).
5. Use MP potion: Increases the protagonist's MP by $DMP$ (up to the maximum).

After the protagonist's action, the Boss attacks the protagonist, reducing the protagonist's HP by $A_i$ in the $i$-th round.

Initially, the protagonist's HP, MP, and SP are all at their maximum values. The protagonist dies if their HP becomes $\le 0$.

If the protagonist can kill the Boss within these $N$ rounds, output "Yes" followed by the earliest round number in which the Boss can be killed, separated by a space.

If the protagonist is guaranteed to be killed by the Boss, output "No".

In all other cases, output "Tie".

Input

The first line contains an integer $T$, the number of test cases.

Each test case consists of the following:

The first line contains nine integers $N$, $M$, $HP$, $MP$, $SP$, $DHP$, $DMP$, $DSP$, $X$.

The second line contains $N$ integers $A_i$.

The third line starts with an integer $N_1$, followed by $N_1$ pairs of integers $B_i$, $Y_i$.

The fourth line starts with an integer $N_2$, followed by $N_2$ pairs of integers $C_i$, $Z_i$.

Output

Output $T$ lines, each containing the answer for the corresponding test case.

Examples

Input 1

2
5 100 100 100 100 50 50 50 20
50 50 30 30 30
1 100 40
1 100 40
5 100 100 100 100 50 50 50 10
50 50 30 30 30
1 100 40
1 100 40

Output 1

Yes 4
Tie

Note 1

For the first example, the protagonist's strategy is: first round spell attack, second round use HP potion, third round special skill attack, fourth round normal attack.

Constraints

For $10\%$ of the data: $N \le 10$, $N_1 = N_2 = 0$.

For $30\%$ of the data: $N \le 10$, $N_1 = N_2 = 1$.

For $60\%$ of the data: $N \le 100$, $M \le 10\,000$, $HP,MP,SP \le 70$.

For $100\%$ of the data: $1 \le N \le 1\,000$, $1 \le M \le 1\,000\,000$, $1 \le HP,MP,SP \le 1\,000$, $N_1,N_2 \le 10$, $DHP,A_i \le HP$, $DMP,B_i \le MP$, $DSP,C_i \le SP$, $X,Y_i,Z_i \le 10\,000$, $1 \le T \le 10$.