I implemented avl tree and works correctly, if keys are different or duplicates are not so much. When i try to insert or delete 10000 times random keys in range [0;5] in some moment tree becomes not avl. Is there any reason that rotations broke avl tree constraints if keys duplicates?

Can someone explain me the idea of the solution of 1989 task from a last timus — > http://acm.timus.ru/problem.aspx?space=1&num=1989 ?

Two players playing a game. Peter has a dice with N walls ( numbered from 1 to N ), Sam has a dice with M walls ( numbered from 1 to M ). Before the game on random they select two numbers L ( L <= N ) and K ( K <= M ). If a during the game Peter throw any of his L numbers he wins. If a Sam throw any of his K numbers — he wins the game. They change off on each turn while someone win. The first turn is for Peter. What is the probability Peter to win the game?

Input

The first line has four numbers — 1 <= N, L, M, K <= 1000. The second line has L numbers — the winning numbers for Peter, 1 <= Ai <= N. The third line has K numbers — the winning numbers for Sam, 1 <= Bi <= M.

Output

The probability Peter to win the game like a rational fraction. The output fraction must be simplified ( if the fraction is 2/4, we must output 1/2 ). The numbers 0 and 1, will be represent like a 0/1 and 1/1.

Input

2 1 6 2

1

1 2

Output

3/4

Can someone explain me the solution of problem?

http://www.codechef.com/problems/MULTQ3;