1931 - 数对排序
Description

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

我们对所有的有序数对进行排序,排序规则如下:

  • 首先,计算每个数对的两数之和,和较小的数对靠前排列;

  • 其次,如果两数之和一样大,则数对中第一项较小的数对靠前排列。

按照这个规则排序,前 66 项数对为

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

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


Input
  • 单个整数 k


Output
  • 两个整数:表示第 k 个有序数对


Examples

Input

6

Output

2 0
Hint
  • 30% 的数据,1≤�≤1,0001k1,000

  • 60%60% 的数据,1≤�≤1,000,0001k1,000,000

  • 100%100% 的数据,1≤�≤1,000,000,0001k1,000,000,000


题目参数
Time Limit 1 second
Memory Limit 128 MB
提交次数 22
通过次数 13