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.

题目描述

现有一个存储整数对（Pair）的容器，支持以下操作：插入整数对、查询指定索引的整数对、修改指定索引的整数对、按第一元素升序排序、按第二元素升序排序和反转容器。你需要实现这个容器，并处理可能的边界情况。具体规则如下：

1. 插入操作：在容器末尾添加一个整数对。
2. 查询操作：获取指定索引位置的整数对。
3. 修改操作：修改指定索引位置的整数对。
4. 第一元素排序：按整数对的第一元素升序排序，若第一元素相同则按第二元素升序排序。
5. 第二元素排序：按整数对的第二元素升序排序，若第二元素相同则按第一元素升序排序。
6. 反转操作：反转容器中所有整数对的顺序。

操作完成后，需输出最终容器中的所有整数对（按存储顺序）。

输入格式

• 第一行输入一个整数q（1 ≤ q ≤ 100000），表示操作的总次数。
• 接下来q行，每行表示一次操作，格式如下：
  • 插入操作：1 a b（插入整数对(a, b)）。
  • 查询操作：2 idx（查询索引为idx的整数对，索引从0开始）。
  • 修改操作：3 idx a b（将索引为idx的整数对修改为(a, b)）。
  • 第一元素排序：4（按第一元素升序排序）。
  • 第二元素排序：5（按第二元素升序排序）。
  • 反转操作：6（反转容器顺序）。

输出格式

• 对于每次查询操作（操作2），输出一行：
  • 若索引合法，输出对应的整数对a b；
• 所有操作完成后，输出多行：
  • 每行包含两个整数a b，表示容器中的一个整数对，按存储顺序输出。
  • 若容器为空，不输出任何行。

样例 1 输入

6
1 3 2
1 1 4
1 2 1
4
2 0
2 2

样例 1 输出

1 4
3 2
1 4
2 1
3 2

样例说明

1. 插入操作：依次插入(3, 2)、(1, 4)、(2, 1)，容器变为[(3, 2), (1, 4), (2, 1)]。
2. 第一元素排序：按第一元素升序排序后，容器变为[(1, 4), (2, 1), (3, 2)]。
3. 查询操作：索引0的整数对为(1, 4)，输出1 4。
4. 查询操作：索引2的整数对为(3, 2)，输出3 2。
5. 最终输出：按存储顺序输出所有整数对1 4、2 1、3 2。

测试点约束

• 操作次数 q ≤ 100000。
• 所有整数对的元素取值范围为int（-2^31 ~ 2^31-1）。
• 所有索引idx均为非负整数。
• 4 5 6操作一共最多出现一次
• 保证所有操作合法

提示

• 排序规则：排序时需严格按照题目指定的优先级（如第一元素优先、第二元素次之）。
• 边界检查：查询和修改操作需检查索引是否合法。
• 高效实现：排序操作的时间复杂度应为O(n log n)。