Keep Outer Loop Running

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

For each i=1..n, find the smallest j in [1,m] with i*j>=K; print i and j, or i -1 if none. Do not stop the outer loop after the first hit.

Input

One line: n,m,K, where 1<=n,m<=100 and 1<=K<=10000.

Output

Exactly n lines: i and the smallest valid j, or -1.

Subtasks

• Subtask 1 (20%): $1\le n\le 10$; $1\le m\le100$; $1\le K\le10000$.

• Subtask 2 (30%): $1\le n\le 40$; $1\le m\le100$; $1\le K\le10000$.

• Subtask 3 (50%): $1\le n\le 100$; $1\le m\le100$; $1\le K\le10000$.

Examples

Example 1

Input:

3 4 6

Output:

1 -1
2 3
3 2

Explanation:

For each i, the first j in ascending order meeting product >=K is minimal. Result: 1 -1 2 3 3 2.

Example 2

Input:

1 2 1

Output:

1 1

Explanation:

For each i, the first j in ascending order meeting product >=K is minimal. Result: 1 1.