問題文

先日、Vil君が司会を務めるクイズ大会が開催されました。大会のルールは以下のようなものです。

• 開始時点で参加者の点数は全員 $0$ である。
• 人 $i$ が正答したとき、人 $i$ の点数が $1$ 増加する。
• 人 $i$ が誤答したとき、それが人 $i$ の $D$ 回目の誤答であるとして、人 $i$ の点数が $D$ 減少する(点数に下限はない)。
• 最終時点で人 $i$ より真に点数が大きい人の人数を $R$ として、人 $i$ は $R+1$ 位となる。

この大会には $N$ 人が参加し、$N$ 人合計で $A$ 回の正答と $W$ 回の誤答があったことが分かっています。このとき $K$ 位の人の点数として考えられる最大値を求めてください。どのような結果であっても $K$ 位が現れない場合はそのことを報告してください。

$T$ 個のテストケースそれぞれについて答えてください。

入力

$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$

• 入力はすべて整数
• $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$

出力

各テストケースに対し、どのような結果であっても $K$ 位が現れない場合は :( を、そうでない場合は $K$ 位の人の点数として考えられる最大値を出力し、改行してください。

サンプル

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

4
0
:(

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