This is the hard version of the problem. The differences between the two versions are the constraints on all the variables. You can make hacks only if both versions of the problem are solved. Tsovak and Narek are playing a game. They have an array (a) and a matrix (b) of integers with (n) rows and (m) columns, numbered from (1). The cell in the (i)-th row and the (j)-th column is ((i, j)). They are looking for the elements of (a) in turns; Tsovak starts first. Each time a player looks for a cell in the matrix containing the current element of (a) (Tsovak looks for the first, then Narek looks for the second, etc.). Let's say a player has chosen the cell ((r, c)). The next player has to choose his cell in the submatrix starting at ((r + 1, c + 1)) and ending in ((n, m)) (the submatrix can be empty if (r=n) or (c=m)). If a player cannot find such a cell (or the remaining submatrix is empty) or the array ends (the previous player has chosen the last element), then he loses. Your task is to determine the winner if the players play optimally. Note: since the input is large, you may need to optimize input/output for this problem. For example, in C++, it is enough to use the following lines at the start of the main() function: The first line of the input contains (t) ((1 \le t \le 1500)) – the number of test cases. The first line of each test case contains three integers (l), (n), and (m) ((1 \le l, n, m \le 1500)) – the size of the array and the sizes of the matrix. The second line contains (l) integers (a_1, a_2, a_3, \ldots a_l) ((1 \le a_i \le n \cdot m)) – the elements of the array (a). The (i)-th of the last (n) lines contains (m) integers (b_{i,1}, b_{i,2}, b_{i,3}, \ldots b_{i,m}) ((1 \le b_{i,j} \le n \cdot m)) – representing the (i)-th row of the matrix. It is guaranteed that the sum of (n \cdot m) over all test cases does not e