“欢迎来到魔术秀！您即将欣赏到魔术师 Ivor 带来的精彩魔术表演。”这就是 Ivor 脑海中对自己第一场魔术表演开场白的美好畅想，但在此之前，他需要做好准备。

Ivor 将邀请 $n$ 位志愿者来配合他的魔术，并将他们安排在舞台上。队伍的最左端是第 1 个人，第 1 个人的右边是第 2 个人，第 2 个人的右边是第 3 个人，依此类推。

Ivor 在准备过程中学习的魔术可以表示为 $l$ $r$ $len$ 的形式。通过这样一个魔术，Ivor 可以交换人们的位置，具体来说，是交换两个长度相等且不相交的区间：区间 $[l, l + len - 1]$ 和区间 $[r, r + len - 1]$。如果两个区间没有共同的志愿者，则称它们是不相交的。

Ivor 经常会想，对于给定的某个人 $x$，如果他可以按任意顺序、任意次数使用已学会的魔术，那么这个人可以达到的最小和最大位置分别是什么。他也不一定需要使用目前学会的所有魔术。

共有 $Q$ 个事件描述 Ivor 的准备过程，事件分为以下两种类型：

• 类型为 1 x 的事件：要求你根据 Ivor 目前学会的魔术来回答他的问题。他可以按任意顺序使用这些魔术，且不需要使用所有魔术。
• 类型为 2 l r len 的事件：表示 Ivor 刚刚学会了一个新魔术。

你的任务是帮助 Ivor 并回答所有第一类型的事件。

输入格式

第一行包含两个自然数 $n$ 和 $q$ （$1 \le n, q \le 2 \cdot 10^5$），含义如题目描述中所述。

接下来的 $Q$ 行中，每行描述一个事件，格式为以下之一：

• 1 x —— Ivor 想要知道第 $x$ 个人可以达到的最小和最大位置（$1 \le x \le n$）。
• 2 l r len —— Ivor 学会了交换区间 $[l, l + len - 1]$ 和 $[r, r + len - 1]$。保证 $1 \le len \le n$，$l + len - 1 < r$ 且 $r + len - 1 \le n$。

输出格式

对于每个类型为 1 的事件，输出两个数，分别表示该人可以达到的最小和最大位置，用一个空格隔开。

子任务

样例

输入样例 1

5 3
2 3 4 1
1 5
1 3

输出样例 1

5 5
3 4

输入样例 2

9 2
2 1 7 2
1 2

输出样例 2

2 8

说明

第二个样例的解释：Ivor 学会了交换区间 $[1, 2]$ 和 $[7, 8]$。第 2 个人可以达到的最小位置是 2。第 2 个人可以达到的最大位置是 8，因为 Ivor 可以交换区间 $[1, 2]$ 和 $[7, 8]$。