Problem Statement

The other day, a quiz competition hosted by Vil was held. The rules of the competition are as follows.

• At the start, every participant has a score of $0$.
• When person $i$ answers correctly, person $i$'s score increases by $1$.
• When person $i$ answers incorrectly, and this is person $i$'s $D$-th incorrect answer, person $i$'s score decreases by $D$ (there is no lower limit on the score).
• Let $R$ be the number of people whose final score is strictly greater than that of person $i$. Then person $i$ is ranked $R+1$-th.

$N$ people participated in this competition, and it is known that the $N$ people gave a total of $A$ correct answers and $W$ incorrect answers. Find the maximum possible score of a person ranked $K$-th. If rank $K$ cannot appear under any outcome, report that.

Answer each of the $T$ test cases.

Input

$T$
$N_1\ A_1\ W_1\ K_1$
$N_2\ A_2\ W_2\ K_2$
$\vdots$
$N_T\ A_T\ W_T\ K_T$

• All inputs are integers.
• $1 \le T \le 100$
• $2 \le N_t \le 2 \times 10^5$
• $0 \le A_t,W_t \le 10^9$
• $1 \le K_t \le N_t$
• $\displaystyle \sum_{t=1}^{T}N_t \le 2 \times 10^5$

Output

For each test case, if rank $K$ cannot appear under any outcome, print :(; otherwise, print the maximum possible score of a person ranked $K$-th. End each output with a newline.

Sample

3
4 9 3 2
7 8 1 7
7 1 0 6

4
0
:(

$1:\ $ooooo
$2:\ $oooo
$3:\ $x 
$4:\ $xx