You are playing a monster-slaying game. The game takes place on a map, and your task is to wield weapons to defeat all the monsters on the map.

The map consists of $n$ cities and $m$ undirected roads connecting these cities, such that all cities are connected either directly or indirectly. Each city has a monster, and the health of the monster in city $i$ is $a_i$.

Initially, you have $k$ weapons, and the $i$-th weapon has a durability of $b_i$.

You can choose any city to start from and travel along the roads. Every time you arrive at a city for the first time, you must fight the monster there. The rules of combat are: you use the weapons you have in the order of their indices. If the current durability of the weapon is not less than the monster's health, you can kill the monster, but the weapon's durability will decrease by an amount equal to the monster's health. If the current weapon's durability is less than the monster's health, you cannot use this weapon to fight the monster; you must immediately discard it and switch to the next one. If you have no more weapons to switch to, you lose the game.

Additionally, there are $q$ items on the map, distributed in different cities. The $i$-th item is located in city $c_i$ and has an attribute value of $d_i$. Every time you kill a monster in a city, if there is an item in that city, you obtain it. The effect of an item is that when you fight a monster, you can use one item on it beforehand to reduce the monster's health by $d_i$, down to a minimum of $0$. Each item can be used at most once, and each monster can have at most one item used on it. Note that items do not need to be used immediately after being obtained.

Can you defeat all the monsters? If you can, find the optimal strategy (i.e., minimize the number of weapons used $x$, and if there is a tie, maximize the remaining durability $y$ of the last weapon used), and output $x$ and $y$. If you cannot win, simply output the string FAIL.

Input

The first line contains $4$ non-negative integers $n, m, k, q$.

The next $m$ lines each contain $2$ positive integers $u_i, v_i$, representing a road connecting city $u_i$ and city $v_i$.

The next line contains $n$ positive integers $a_i$, representing the health of the monsters.

The next line contains $k$ positive integers $b_i$, representing the initial durability of the weapons.

The next $q$ lines each contain $2$ positive integers $c_i, d_i$, describing an item.

Output

Output a single line. If a winning strategy exists, output $2$ positive integers $x$ and $y$, representing that the first $x$ weapons were used in the optimal strategy, and the remaining durability of the last weapon used is $y$. If you cannot win, output the string FAIL.

Examples

Input 1

3 2 2 2
1 2
2 3
2 3 5
2 6
2 2
3 3

Output 1

2 1

Note 1

Your optimal strategy is to fight the monster in city $3$ first. Although you will discard weapon $1$ immediately, you can then use the items to defeat the monsters in city $2$ and city $1$ without consuming any durability. If you choose to fight the monster in city $1$ first, weapon $2$ will have $0$ durability left at the end.

Input 2

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

Output 2

FAIL

Note 2

Because you cannot use both items on the monster in city $3$, you cannot defeat it regardless of your strategy.

Subtasks

For all data, $1 \leq n \leq 18$, $n-1 \leq m \leq n(n-1)/2$, $1 \leq k \leq n$, $0 \leq q \leq \min(n, 8)$, $1 \leq a_i, b_i \leq 10^9$, $1 \leq c_i \leq n$, $1 \leq d_i \leq 10^9$, $1 \leq u_i, v_i \leq n$, $u_i \neq v_i$. It is guaranteed that all $c_i$ are distinct, that there is at most one road directly connecting any pair of cities, and that the given graph is connected.