Xor Table

All submissions for this problem are available.
###Read problems statements in [Hindi](http://www.codechef.com/download/translated/S19ELTST/hindi/XORTABLE.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/S19ELTST/mandarin/XORTABLE.pdf), [Russian](http://www.codechef.com/download/translated/S19ELTST/russian/XORTABLE.pdf), [Vietnamese](http://www.codechef.com/download/translated/S19ELTST/vietnamese/XORTABLE...) and [Bengali](http://www.codechef.com/download/translated/S19ELTST/bengali/XORTABLE.pdf) as well. There are two integer sequences $A_1, A_2, \dots, A_N$ and $B_1, B_2, \dots, B_M$. You do not know the exact values of their elements, but you know that $L_i \le A_i \le R_i$ for each valid $i$ and $P_i \le B_i \le Q_i$ for each valid $i$. You also have a matrix $C$ with $N$ rows and $M$ columns. Some elements of $C$ are missing. For each element $C_{i, j}$ ($1 \le i \le N$, $1 \le j \le M$) that is not missing, you know that $C_{i, j} = A_i \oplus B_j$ ($\oplus$ denotes bitwise XOR). Your task is to find two sequences $A$ and $B$ satisfying all given conditions. If multiple solutions exist, you may find any one. ### Input  The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.  The first line of each test case contains two spaceseparated integers $N$ and $M$.  $N$ lines follow. For each $i$ ($1 \le i \le N$), the $i$th of these lines contains two spaceseparated integers $L_i$ and $R_i$.  $M$ lines follow. For each $i$ ($1 \le i \le M$), the $i$th of these lines contains two spaceseparated integers $P_i$ and $Q_i$.  $N$ more lines follow. For each $i$ ($1 \le i \le N$), the $i$th of these lines contains $M$ spaceseparated integers $C_{i, 1}, C_{i, 2}, \dots, C_{i, M}$. Missing elements are denoted by $1$. ### Output For each test case:  If no solution exists, print a single line containing the string `"NO"`.  Otherwise, print three lines. The first line should contain the string `"YES"`. The second line should contain $N$ spaceseparated integers $A_1, A_2, \dots, A_N$. The third line should contain $M$ spaceseparated integers $B_1, B_2, \dots, B_M$. ### Constraints  $1 \le T \le 100$  $1 \le N, M \le 10^3$  the sum of $N \cdot M$ over all test cases does not exceed $10^6$  $0 \le L_i \le R_i \lt 2^{30}$ for each valid $i$  $0 \le P_i \le Q_i \lt 2^{30}$ for each valid $i$  $1 \le C_{i, j} \lt 2^{30}$ for each valid $i, j$ ### Example Input ``` 2 3 3 2 4 3 4 4 6 1 3 4 7 6 8 2 7 4 5 0 3 4 1 2 2 2 4 6 5 7 3 9 2 4 3 6 6 5 ``` ### Example Output ``` YES 3 4 5 1 4 7 NO ```Author:  kingofnumbers 
Editorial  https://discuss.codechef.com/problems/XORTABLE 
Tags  backtracking, bitwiseoperatn, constructive, graph, kingofnumbers, mediumhard, snckel19, taran_1407 
Date Added:  24052018 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 