题目描述

给定一个序列的总长度 $n$。

请你找出该序列中所有的连续子区间，并输出它们的左右端点下标。在输出时，必须严格遵守以下规则顺序输出：

1. 首先按照子区间的长度从小到大进行输出；
2. 如果长度相同，则按照子区间的左端点从小到大进行输出。

本题中下标从 $1$ 开始。

输入格式

输入仅包含一行，一个正整数 $n$ —— 表示序列的总长度。

输出格式

输出若干行，每行包含两个正整数 $l$ 和 $r$，分别表示一个子区间的左端点和右端点，中间用一个空格隔开。要求输出顺序严格满足题目描述中的排序规则。

样例输入 1

3

样例输出 1

1 1
2 2
3 3
1 2
2 3
1 3

样例输入 2

2

样例输出 2

1 1
2 2
1 2

说明

样例解释

在第一个样例中，序列总长度为 $3$。

• 长度为 $1$ 的子区间有：$[1, 1], [2, 2], [3, 3]$，按照左端点从小到大输出；
• 长度为 $2$ 的子区间有：$[1, 2], [2, 3]$，按照左端点从小到大输出；
• 长度为 $3$ 的子区间有：$[1, 3]$。

最终将上述区间依次输出即可。

数据范围

• 对于所有测试点，保证 $1 \le n \le 500$。
• 保证所有的输入数值均为整数。