DreamGrid 在他的右口袋里发现了一个包含 $n$ 个顶点且没有边的无向简单图（即一个包含 $n$ 个孤立顶点的图），顶点编号从 $1$ 到 $n$。现在他想对该图执行 $q$ 次以下两种类型的操作：

• $1 \ a \ b$ —— 用一条边连接第 $a$ 个顶点和第 $b$ 个顶点。保证在执行此操作前，不存在直接连接顶点 $a$ 和 $b$ 的边。
• $2 \ k$ —— 回答查询：在图中添加 $k$ 条新边后，连通分量的最小和最大可能数量是多少？注意，添加 $k$ 条边后，图仍必须是简单图，且该查询不会修改图本身。

请帮助 DreamGrid 对每种第二类操作给出答案。回想一下，简单图是指没有自环和重边的图。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含两个整数 $n$ 和 $q$ ($1 \le n \le 10^5, 1 \le q \le 2 \times 10^5$)，分别表示顶点数和操作数。

接下来的 $q$ 行中，第 $i$ 行首先包含一个整数 $p_i$ ($p_i \in \{1, 2\}$)，表示第 $i$ 次操作的类型。

• 若 $p_i = 1$，后面跟着两个整数 $a_i$ 和 $b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$)，表示第一类操作。保证在执行此操作前，不存在直接连接顶点 $a$ 和 $b$ 的边。
• 若 $p_i = 2$，后面跟着一个整数 $k_i$ ($0 \le k_i \le \frac{n(n-1)}{2}$)，表示第二类操作。保证在图中添加 $k_i$ 条边后，该图仍可能成为一个简单图。

保证所有测试数据中 $n$ 的总和不超过 $10^6$，且所有测试数据中 $q$ 的总和不超过 $2 \times 10^6$。

输出格式

对于每个第二类操作，输出一行，包含两个由空格分隔的整数，分别表示该查询下连通分量的最小和最大可能数量。

样例

样例输入 1

1
5 5
1 1 2
2 1
1 1 3
2 1
2 3

样例输出 1

3 3
2 3
1 2