This is the hard version of the problem. The only differences between the two versions are the constraints on (m) and (q). In this version, (m, q \le 10^5). You can make hacks only if both versions of the problem are solved. Narek and Tsovak were busy preparing this round, so they have not managed to do their homework and decided to steal David's homework. Their strict teacher noticed that David has no homework and now wants to punish him. She hires other teachers to help her catch David. And now (m) teachers together are chasing him. Luckily, the classroom is big, so David has many places to hide. The classroom can be represented as a one-dimensional line with cells from (1) to (n), inclusive. At the start, all (m) teachers and David are in distinct cells. Then they make moves. During each move David goes to an adjacent cell or stays at the current one. Then, each of the (m) teachers simultaneously goes to an adjacent cell or stays at the current one. This continues until David is caught. David is caught if any of the teachers (possibly more than one) is located in the same cell as David. Everyone sees others' moves, so they all act optimally. Your task is to find how many moves it will take for the teachers to catch David if they all act optimally. Acting optimally means the student makes his moves in a way that maximizes the number of moves the teachers need to catch him; and the teachers coordinate with each other to make their moves in a way that minimizes the number of moves they need to catch the student. Also, as Narek and Tsovak think this task is easy, they decided to give you (q) queries on David's position. In the first line of the input, you are given a single integer (t) ((1 \le t \le 10^5)) — the number of test cases. The description of each test case follows. In the first line of each test case, you are given three integers (n), (m), and (q) ((3 \le n \le 10^9), $$$1 \le m, q \le 1