# #631. 【UR #21】士兵调度

### 样例一

#### input

4 3 4



#### output

4
0 0
1 1
2 2
3 3
3
0 0 1
1 2 1
1 0 3



### 数据范围

$1$ $10^3$ $10^3$ $10^3$ $40$
$2$ $10^5$ $300$ $94500$ $20$
$3$ $5\times 10^4$ $13600000$ $20$
$4$ $10^5$ $21100000$ $20$