Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 9 Accepted Submission(s) : 3
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
Viewer discretion is advised. The following problem is very academic and that should not be understood by anyone.An undirected graph is a graph in which the nodes are connected by undirected arcs.
An undirected arc is an edge that has no direction. Both ends of an undirected arc are equivalent. We denote an undirected arc between node A and B as A-B.
A directed graph is a graph in which the nodes are connected by directed arcs.
A directed arc is an edge that has direction. One of the endpoints of a directed arc is called the head endpoint and the other is called tail endpoint. We denote a directed arc between node A and B As A->B, in which A is head endpoint and B is the tail endpoint.
For a node, the number of head endpoints adjacent to a node is called the indegree of the node.
An orientation of an undirected graph is a transformation which turns the graph into a directed graph by assigning each arc a direction. We notate the original undirected graph as G:=(V,E) and the transformed directed graph as G':=(v',E').
A transitive orientation of an undirected graph is an orientation which satifies the following constraint:
For any three distinct nodes A,B and C
由A->B属于E'并且B->C属于E'推出A->C属于E'.
An undirected graph is called a comparability graph iff it has a transitive orientation.
In 1977 an algorithm was designed to check if a given graph is comparability graph with complexity O(d*|E|), where d is the maximum degree of nodes. And in 2000 a paper presented a new algorithm solving the same problem in O(|E|*log2|V|). Both algorithm return a transitive orientation of the inputted graph if it is found to be comparability graph.
A complete graph is an undirected graph in which each pair of nodes is connected by an edge. It is trivial that all complete graphs are comparability graphs, because complete graths never contain chordless cycle.
ICTOP(indegree-constrained-transitive-orientation-problem) is to find a transitive orientation of an undirected graph under the upper-bound indegree of each node. In the case that such orientation doesn't exist, the problem aims at finding the transitive orientation which maximize the number of nodes whose indegree doesn't exceed the corresponding upper-bound. In the case that no transitive orientation exists, the problem aims at outputting "Oops" in a single line.
However, here comes the problem.
Z is so stupid that he doesn't understand the above bullshit at all. To spare his professional time on the contest, he decides to draw pictures on the test paper.
As you can see, the test paper is full of bullshit and there's just too little room left for painting arts. Z wonders if he could have enough room for an X*Y size painting. To generalize the problem, he divides the test paper into N*M grids. Each grid is either empty or occupied. He wonders if there's an X*Y sub-grid which contains no occupied grid. Can you help him?
Input
First line of the input contains a positive integer, indicating the number of test cases.Each test case starts with a line containing 2 integers N and M(1<=N,M<=1000)
The next N lines each contain M integers. Each integer is either 0, which means the corresponding grid is empty, or 1, which means it's occupied.
Next line is an integer K(K<=1000000), indicating the number of Z's queries.
Each of the next K lin