H. Brass Birmingham: roads
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Today Igor and Ira with friends — Sasha and Lesha — decided to play a new board game "Brass Birmingham".

In each round, the players take turns making moves. During the turn, the player can build one industry per city, a road connecting two cities, or perform an action.

The game ended late at night, and it was time to sum up the results. Igor was in charge of counting points for building roads. Each road built by the player earns him several points equal to the total number of industries opened in the cities connected by this road.

Unfortunately, Igor accidentally knocked over the playing field so that all the cards got mixed up. Igor was disappointed. He remembered that during the game, he wrote down the actions of each player in a notebook. Help Igor count the points for the roads received by each player.

Input

The first string contains an integer $$$N$$$ $$$(2\leq N\leq 10^5)$$$ — the number of cities in the game.

Next, for each of the four players, it is indicated:

The first string contains integers $$$M_k,G_k$$$ $$$(1\leq M_k,G_k\leq 10^4)$$$ — the number of industries and the number of roads built by the $$$k$$$ player.

In the next string $$$M_k$$$ of integers $$$m_{ki}$$$ $$$(1\leq m_{ki}\leq N)$$$ — the cities where the industries of the $$$k$$$ player are located.

Then $$$G_k$$$ strings, each of which contains two integers $$$a_{ki},b_{ki}$$$ $$$(1\leq a_{ki},b_{ki}\leq N)$$$ — cities that are connected by the road of the $$$k$$$ player.

Output

Print $$$4$$$ integers separated by a space – the number of points for the roads that each player received.

Example
Input
4
1 1
1
1 2
3 1
1 2 3
2 3
4 2
1 4 2 3
3 1
4 2
1 4
3
1 3
2 3
3 4
1 2
Output
5 5 9 20