Chef and Bipartite Graph#11343
The Chef has become interested in studying bipartite graphs. Today, he wants to construct a bipartite graph with vertices in each of the two parts and a total number of edges equal to . The vertices in the left part are numbered from to , and the vertices in the right part are also numbered from to .
The Chef also wants the degree of each vertex to be at least and at most , i.e., for every vertex the following condition must hold:
Given four integers n, m, d, D, you are required to help the Chef construct a bipartite graph satisfying the described conditions. If such a graph does not exist, print .
The first line contains the number of test cases . Each test case consists of a single line containing four integers: n~(1 \le n \le 100), m~(0 \le m \le n \cdot n), d, D~(1 \le d \le D \le n).
For each test case, print if there does not exist a bipartite graph satisfying the given conditions. Otherwise, print lines, each containing two integers and , denoting an edge between vertex in the left part and vertex in the right part.
If there are multiple valid solutions, you may print any of them. Note that the graph must not contain multiple edges.
Example 1