题目描述

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

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

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

按照这个规则排序，前 6 项数对为

(0,0),(0,1),(1,0),(0,2),(1,1),(2,0)

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

输入格式

• 单个整数 k

输出格式

• 单独一行：两个整数表示第 k 个有序数对

数据范围

• $30\%$的数据，$1≤k≤{10}^{3}$
• $50\%$ 的数据，$1≤k≤{10}^{6}$
• $70\%$ 的数据，$1≤k≤{10}^{9}$
• $100\%$的数据，$1≤k≤{10}^{18}$

样例数据

6

2 0