eolymp
bolt
Try our new interface for solving problems

Game

Time limit 1 second
Memory limit 64 MiB

Petya and Vasya are playing a game. The rules are as follows: the game is divided into rounds. Each round, a coin is thrown; if there’s heads – Peter gains a point, if there’s tails – the point is awarded to Vasya. The first who gets N points is the winner and gets all the stamps at stake and the game continues until the winner is determined. The stakes are made before the game starts.

In the middle of the game the bell rings and the boys quit. Help Petya and Vasya to fairly divide the stamps if you know how many stamps were at stake and how many points each of the boys had. “Fairly” means that the stamps are divided in proportion to the chances to win that each player had when the game stopped.

Input data

The first line contains the number of tests. Each of the following lines represents a test and contains four numbers N, k1, k2, S separated by a space. N is the number of points to win (1 <= N <=50), k1 and k2 are the points that Petya (k1) and Vasya (k2) had (0 <= k1, k2 < N), S is a number of stamps that were at stake 1 < S < 10^100).

In the first example (31216), the first player has 2 points left to win, and the second has only one. The second player’s possibility to win is ½ + ¼ = ¾ , and the first player’s chances are ¼. Thus, the first player gets ¼ of the stamps and the second gets ¾.

Output data

For each test, a line that contains two space-separated numbers are written into the output file. The numbers indicate how many stamps Petya and Vasya should get, correspondingly. It is guaranteed that the stamps can be divided fairly with respect to the chances for winning. The possibilities of tails and heads are identical and equal to ½.

Examples

Input example #1
3
3 1 2 16
4 1 1 2
5 1 4 32
Output example #1
4 12
1 1
2 30