Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.
Submit All submissions Best solutions PDF Back to list

EIFBIPARTIE - Complete Bipartite

Given the complete bipartite graph with the number of vertices in two distinct subsets are n and m. Output the list of edges in the lexicographic order

Input

The first line contains two integers n, m (0 < n, m ≤ 103).

The second line contains n distinct integers ai (0 ≤ ai ≤ 109) that represent vertices of the first subset

The second line contains m distinct integers bj (0 ≤ bj ≤ 109 that represent vertices of the second subset.

* 50% of test cases has (0 ≤ ai ≤ n-1, n ≤ bj ≤ n+m-1).

* 90% of test cases has (0 ≤ ai, bj ≤ n+m-1).

Output

Output the edges of the graph in lexicographic order.

Sample

Input

Output

3 2

0 3 1

4 2

0 2

0 4

1 2

1 4

2 3

3 4

3 2

0 1 2

3 4

0 3

0 4

1 3

1 4

2 3

2 4
Submit solution!
Added by:Ha Minh Ngoc
Date:2019-07-19
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: GOSU
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.