Statement

杰瑞米使用自己的权能 「题目生成」生成了下面一个题目

给定正整数 $C$ ，要求使用不超过 $limV$ 个点并且不超过 $limE$ 条有向边构建一个有向图，满足以 $n$ 为根的内向生成树的个数为 $C$。

杰瑞米不知道自己是生成了一个签到题，还是送分题，便指派小 D 去做出这道题，然后向祂报告难度。

小 D 作为一个没什么 oi 水平底层群员，怎么可能会杰瑞米的神仙题，便苦苦哀求你，希望你能帮他解决这道题目。

Task

input

仅一行三个正整数 $C,limV, limE$。

可以证明在给定限制下总是存在解。

output

第一行两个整数 $n, m$，表示你找到的有向图的点数和边数。你需要将你的有向图中的点依次标号为 $1,2,\cdots, n$。

接下来有 $m$ 行，每行有两个正整数 $u,v$ 表示有一条从 $v$ 到 $u$ 的有向边。

注意你的输出可以包含重边。

Sample I

input

1 114514 1919810

output

3 4
1 2
2 1
2 3
3 2

Constraints

本题共 $5$ 个子任务，你需要通过一个子任务内的所有测试点才能取得这个子任务的分数。

对于所有数据满足 $1 \le C \le 10^{18}$ 。