You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

由两个自然数组成的一对数称之为有序数对。有序是指数对的第一项与第二项是区别的，例如 $(0,1)，(1,0)$ 是不一样的数对。

我们对所有的有序数对进行排序，排序规则如下：

• 首先，计算每个数对的两数之和，和较小的数对靠前排列；
• 其次，如果两数之和一样大，则数对中第一项较小的数对靠前排列。

按照这个规则排序，前 $6$ 项数对为 $(0,0), (0,1), (1,0), (0,2), (1,1), (2,0)$

给定一个整数 $𝑘$，请求出第 $k$ 个数对。

输入输出格式

输入格式

一行一个整数 $k$。

输出格式

两个整数：表示第 $𝑘$ 个有序数对。

输入输出样例

6

2 0

数据规模

• 对于 30% 的数据， $1 \le k \le 1000$
• 对于 60% 的数据， $1 \le k \le 10^6$
• 对于 100% 的数据， $1 \le k \le 10^9$