Gone are the days Chicken needs to do IO. So much time has already been spent on IO that he needs to touch grass. Very fortunately, there are 2 arrays a and b in front of him. Interestingly, the kth element of array $$$a$$$, $$$a_k$$$ is defined to be grass if $$$$$$\sum_{i = 1}^n |a_k - a_i| \le \sum_{i = 1}^n |b_k - b_i|$$$$$$ Regrettably, Chicken has not touched grass for a long time. Hence he does not know which elements are grass. Luckily you are here to help him find grass, can you help him?
Much to both of your surprise, just as you were about to help him, disaster struck! 1 weird guy named $$$אתבש$$$, who proclaimed himself as Chicken's personal array adjuster showed up and blindfolded the 2 of you, making you unable to see the array, as an act of revenge for failing to get NOI Gold by 1 point before proceeding to get run over by truck-kun. Gravely, Chicken tells you that he wants to touch grass before he dies. Xeric conditions coupled with nearby grass have caused you to lose all your energy, but you are determined to help Chicken fulfill his last wish.
The first line of input is an integer t, representing the index of the testcase. As you are blindfolded, you cannot see the array nor its changes and hence there is no other input. However, the format of the arrays, as well as that of the updates remain the same as in findinggrass.
Before the first update, and after every update, output any integer $$$k$$$ such that $$$a_k$$$ is grass. If there is no such integer, output −1 instead.
For all subtasks, it is guaranteed that:
| Subtask | Score | N | Q | Additional Constraints |
| 1 | 7 | $$$N\leq 2000$$$ | $$$Q\leq 50$$$ | — |
| 2 | 16 | $$$N\leq 2\cdot 10^4$$$ | $$$Q\leq 50$$$ | — |
| 3 | 24 | $$$N\leq 2\cdot 10^4$$$ | $$$Q\leq 10^4$$$ | — |
| 4 | 26 | — | $$$1\leq a_i,b_i,v_i\leq2\cdot 10^5$$$ | |
| 5 | 27 | — | ||
As $$$אתבש$$$ has reincarnated as a spoon in another world, he is unable to provide sample testcases.
As Chicken has dementia, he cannot remember things properly and memory limit is reduced. He will die soon, hence time limit is also reduced.
Chicken's chinese neighbour plays the violin instead of the piano in this version and does not know binary search instead of sorting
While trying to solve the problem, a Rust fan trashes on you for using C++
$$$אתבש$$$ likes golden and legendary numbers
You may not give Chicken up or let him down
You may not take off your blindfolds
Chicken has never been to a Sawcon, though he would love to.
| Subtask | Score |
|---|---|
| 1 | 7 |
| 2 | 16 |
| 3 | 24 |
| 4 | 26 |
| 5 | 27 |