It’s time for the Celestial Ball at Hogwarts. But due to the ongoing pandemic this year, the Ministry of Magic has decided to arrange the Ball to a limited extent. At most $k$ couples will be able to stay and dance in the Great Hall at a time maintaining social distancing. The Ball will continue for $n$ hours and exactly $n$ couples have registered for the Ball.
Before entering the Great Hall, every couple must go through the COVID-19 test conducted by Madam Pomfrey. It takes exactly one hour to get the result of the test. So each hour, exactly one couple will have the test done and enter the Great Hall. But the problem will arise when there will be more than $k$ couples in the Great Hall. So the Ministry has decided that the Goblet of Fire will give every couple a score based on their dancing skill. So every hour before a wizard couple enters the Great Hall and there are already $k$ wizard couples in the hall, the couple with the lowest score will leave the Ball. If there are multiple couples in the hall with the same score, the one who entered the hall first, will also leave first.
Everyone except Lord Voldemort aka You Know Who aka He Who Must Not Be Named was planning their dance moves. Voldemort was planning for his rebirth but wanted to go to the Ball with his crush She Who Must Not Be Named. So Voldemort decided to make poly juice potion and took the form of another wizard. He decided to kill a couple and enter the Great Hall in disguise. He possesses enough power to get away from all the great wizards at the Great Hall, but can not rig the Goblet of Fire. Voldemort may be a great wizard but not a good dancer, so his score may not be the highest. He does not want to kill more than one couple and enter the Ball multiple times. It can raise suspicion, and he does not want to confront the greatest sorcerer in the world, Albus Dumbledore. So, he wants to kill exactly one couple and take their place and pass the maximum time in the Hall.
Voldemort passed his whole academic life gathering Dark Arts knowledge, that his algorithmic or mathematical knowledge is far beyond the reach to solve this problem. Now his accomplices have abducted you to solve the problem. You can not say no or fail to solve it, otherwise …
You must be afraid but If it feels any better, you are given an integer sequence $d_1, d_2, \ldots, d_n$ — the dancing skill scores of the couples according to the order they will do their COVID-19 test and an integer $v$ — the dancing skill score of You Know Who. For each $i$ from $1$ to $n$, you have to find the amount of time Voldemort can spend in the Great Hall if he kills the $i^{th}$ couple and takes their place.
By the way, we have found some good news!!! Thanks to the compact Bio security bubble maintained by the Hogwarts authority and the safety potions made by the potion master Severus Snape, none of the couples will be tested positive for COVID-19.
Input
The first line of the input contains a single integer $t(1 \le t \le 50)$ denoting the number of test cases. The description of $t$ test cases follows.
The first line of each test case contains three space-separated integers $n(1 \le n \le 10^5)$, $k(1 \le k \le n)$ and $v(1 \le v \le 10^5)$ — the number of couples, the maximum capacity of the Great Hall and the dancing skill score of Lord Voldemort respectively.
The next line contains $n$ space-separated integers $d_1, d_2, \ldots, d_n(1 \le d_i \le 10^5)$ — the dancing skill scores of each couple. The couples will enter the Great Hall in the given order.
Output
For each test case, print $n$ space-separated integers — the $i^{th}$ integer is the number of hours Voldemort can spend if he kills the $i^{th}$ couple and takes their place.
Sample
| Input | Output |
|---|---|
2 8 4 3 6 4 5 3 7 2 1 8 8 4 5 6 4 5 3 7 2 1 8 | 4 3 2 1 1 1 1 1 8 4 6 5 4 3 2 1 |
