B"This is a hard version of the problem; it differs from the easy version only by the question. The easy version only needs you to print whether some values are non-zero or not. The hard version needs you to print the exact values. Alice and Bob are dividing the field. The field is a rectangle of size n x m ( 2 <= n, m <= 10^9 ); the rows are numbered from 1 to n from top to bottom, and the columns are numbered from 1 to m from left to right. The cell at the intersection of row r and column c is denoted as ( r, c ). Bob has k ( 2 <= k <= 2 cdot 10^5 ) fountains, all of them are located in different cells of the field. Alice is responsible for dividing the field, but she must meet several conditions: Alice wants to divide the field in such a way as to get as many cells as possible. Bob wants to keep ownership of all the fountains, but he can give one of them to Alice. First, output the integer alpha -- the maximum possible size of Alice's plot, if Bob does not give her any fountain (i.e., all fountains will remain on Bob's plot). Then output k non-negative integers a_1, a_2, ... , a_k , where a_i is a value such that after Bob gives Alice the i -th fountain, the maximum size of her plot will be alpha + a_i . The first line contains a single integer t ( 1 <= t <= 10^4 ) -- the number of test cases. The first line of each test case contains three integers n , m , and k ( 2 <= n, m <= 10^9 , 2 <= k <= 2 cdot 10^5 ) -- the field sizes and the number of fountains, respectively. Then follow k lines, each containing two numbers r_i and c_i ( 1 <= r_i <= n , 1 <= c_i <= m ) -- the coordinates of the cell with the i -th fountain. It is guaranteed that all cells are distinct and none of them is ( n, 1 ). It is guaranteed that the sum of k over all test cases does not exce"...