题目描述

给定包含 $n$ 个结点的完全二叉树，如下图是一棵包含 $n = 6$ 个结点的完全二叉树。

树上的所有节点开始时没有被染色，颜色为 $0$。

给定 $q$ 次操作，操作可以是：

1. $x_i\ y_i\ z_i$，表示将与结点 $x_i$ 距离小于等于 $y_i$ 的结点的颜色全部染成 $z_i$；
2. $x_i$，表示查询结点 $x_i$ 的颜色。

输入格式

输入的第一行包含两个整数 $n, q$，用一个空格分隔。

接下来 $q$ 行，每行包含 $1$ 个操作，相邻的整数之间使用一个空格分隔。保证每个操作都是合法的。

输出格式

对于每个查询操作，输出一行包含一个整数表示对应的答案。

输入输出样例 #1

输入 #1

6 6
1 1 1 1
2 3
1 5 2 2
2 4
2 1
2 3

输出 #1

1
2
2
1

说明/提示

对于 $40\%$ 的评测用例，$n, q \le 5000$；

对于所有评测用例，$1 \le n \le 10^6,1\le q \le 2 \times 10^5,1 \le x_i \le n,1 \le y_i \le 10^6,1 \le z_i\le 10^6$。