{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eNearly all cicadas spend years underground as juveniles, before emerging above ground for a short adult stage of several weeks to a few months.\u003cbr\u003eThe seven periodical cicada species are so named because, in any one location, all of the members of the population are developmentally synchronized they emerge as adults all at once every seven years.\u003cbr\u003eThe lifecycles of most periodical cicada species range from two to seventeen years, although some could be longer.\u003cbr\u003eThere is a forest which can be roughly divided into a matrix of size N ×M. The upper-left region is (1, 1) and the lower-right region is (N, M).\u003cbr\u003eA population of periodical cicadas live within each region of the matrix. The population in region (i, j) emerged in year $a_{i,j}$ for the first time, and re-emerges every $b_{i,j}$ years. i.e. they are $b_{i,j}$ - periodical cicadas.\u003cbr\u003eGiven a selected rectangular area, entomologists wonder if there is a time when all cicadas in that area emerge together.\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line of the input gives the number of test cases, T. T test cases follow. Each test cases begin with two integers N and M.\u003cbr\u003eThe following N lines each consists of M integers $a_{i,j}$ representing the year cicadas emerged in region (i, j) for the first time.\u003cbr\u003eThe following N more lines each consists of M integers $b_{i,j}$ representing the periodical cycle of the cicadas in that region.\u003cbr\u003eThen comes a line with an integer Q representing the number of queries. The following Q lines each consists of 4 integers: $x_1, y_1, x_2, y_2,$ representing the upper-left and lower-right coordinate of the selected rectangular area.\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"For each test case, first output one line containing “Case #x:”, where x is the test case number (starting from 1).\u003cbr\u003eThe following Q lines each consists of an integer which is the year when all cicadas in the selected area emerge together for the first time or -1 if it’s impossible.\u003cbr\u003e\u003ch2\u003elimits\u003c/h2\u003e\u003cbr\u003e$\\bullet 1 ≤ T ≤ 10.$\u003cbr\u003e$\\bullet 1 ≤ N, M ≤ 200.$\u003cbr\u003e$\\bullet 0 ≤ a_{i,j} \u0026lt; b_{i,j} ≤ 40.$\u003cbr\u003e$\\bullet 1 ≤ x_1 ≤ x_2 ≤ N.$\u003cbr\u003e$\\bullet 1 ≤ y_1 ≤ y_2 ≤ M.$\u003cbr\u003e$\\bullet$ 1 ≤ Q ≤ 500000.\u003cbr\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n3 4\r\n3 1 1 2\r\n1 1 2 1\r\n1 0 5 5\r\n5 4 2 3\r\n2 2 3 2\r\n4 2 6 6\r\n5\r\n2 2 2 2\r\n1 1 3 4\r\n1 4 2 4\r\n1 1 1 2\r\n2 2 3 4\r\n1 2\r\n0 1\r\n2 2\r\n1\r\n1 1 1 2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1:\r\n1\r\n-1\r\n5\r\n13\r\n-1\r\nCase #2:\r\n-1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}