Chef and Number Guessing

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef has a rectangular matrix A of nxm integers. Rows are numbered by integers from 1 to n from top to bottom, columns  from 1 to m from left to right. A_{i, j} denotes the jth integer of the ith row.
Chef wants you to guess his matrix. To guess integers, you can ask Chef questions of next type: "How many integers from submatrix i_{L}, i_{R}, j_{L}, j_{R} are grater than or equal to x and less than or equal to y?". By submatrix i_{L}, i_{R}, j_{L}, j_{R} we mean all elements A_{i, j} for all i_{L} ≤ i ≤ i_{R} and j_{L} ≤ j ≤ j_{R}.
Also Chef can answer not more than C questions of next type: "What is the sum of integers from submatrix i_{L}, i_{R}, j_{L}, j_{R}?"
As soon as you think you know the Chefs matrix, you can stop asking questions and tell to the Chef your variant of the matrix. Please see "Scoring" part to understand how your solution will be evaluated.
Input
The first line of the input contains three spaceseparated integers n, m and C denoting the sizes of the matrix and the maximum number of the secondtype questions. After that the judge will answer your questions and evaluate the resuts. Read more about that in the "Interaction with the judge" part of the statement.
Interaction with the judge
To ask a firsttype question you should print to the standard output one line containing seven spaceseparated integers 1 i_{L} i_{R} j_{L} j_{R} x y. To ask a secondtype question you should print one line containing five spaceseparated integers 2 i_{L} i_{R} j_{L} j_{R}. After that you should read from the standard input one integer  answer to the question. To end the game you should print 3 and starting from next line print n lines, each of them contains m spaceseparated integers  your variant of the matrix A. After that your program must stop. Remember to flush the output after every line you print.
Constraints
 1 ≤ n, m ≤ 2.5 * 10^{5}
 1 ≤ n * m ≤ 2.5 * 10^{5}
 10^{3} ≤ C ≤ 10^{4}
 1 ≤ A_{i, j} ≤ 50
 1 ≤ i_{L} ≤ i_{R} ≤ n
 1 ≤ j_{L} ≤ j_{R} ≤ m
 1 ≤ x ≤ y ≤ 50
 0 ≤ number of asked questions ≤ 5 * 10^{5}
 1 ≤ B_{i, j} ≤ 50
 1 ≤ a_{1}, a_{2}, a_{3} ≤ 10
Scoring
Let B will be the matrix you output and diff = ∑ A_{i, j}  B_{i, j} for all 1 ≤ i ≤ n, 1 ≤ j ≤ m. The number of questions you asked is questions. The number of integers, you correctly guessed is correct(i. e. the number of elements i, j such that A_{i, j} = B_{i, j}).
The score for each test case will be: score = a_{1} * questions + a_{2} * diff + a_{3} * (n * m  correct).
Your goal is to minimize this score.
Your total score for the problem will be the sum of scores on all the test cases.
Example
Input: 3 3 10 4 0 3 1 6 Output: 1 1 2 1 2 1 3 1 3 3 1 3 1 1 1 3 3 1 3 2 2 1 1 2 3 3 1 1 2 3 3 1 3 3 2 2 1 2 2 1 2 2 2
Explanation
[1, 2, 3] A = [3, 2, 1] [2, 2, 2]
For this test case a_{1} = 1, a_{2} = 1 and a_{3} = 1.
The score for this test case will be 1 * 5 + 1 * 4 + 1 * (9  6) = 12.
Test data generation
There will be four types of the test files.
 Type #1: n = 10, m = 25000
 Type #2: n = 100, m = 2500
 Type #3: n = 250, m = 1000
 Type #4: n = 500, m = 500
There will be 5 test files of each type. During the contest, you will be shown the score for only one test file of each type.
All elements of matrix A are randomly chosen.
For each test case C is randomly chosen from interval [10^{3} .. 10^{4}].
For each test case values a_{1}, a_{2} and a_{3} are manually chosen.
Author:  antoniuk1 
Editorial  http://discuss.codechef.com/problems/CHNGSS 
Tags  antoniuk1, binarysearch, challenge, march16 
Date Added:  31012016 
Time Limit:  4 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, 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, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions