Background

It is recommended to use PyPy3 to submit this problem.

Problem Description

Given a complete binary tree with $n$ nodes. The figure below shows a complete binary tree with $n = 6$ nodes.

All nodes on the tree are initially uncolored, with color $0$.

There are $q$ operations. Each operation can be:

1. $x_i\ y_i\ z_i$: set the color of all nodes whose distance to node $x_i$ is less than or equal to $y_i$ to $z_i$.
2. $x_i$: query the color of node $x_i$.

Input Format

The first line contains two integers $n, q$, separated by a space.

In the next $q$ lines, each line contains one operation, and adjacent integers are separated by a space. It is guaranteed that every operation is valid.

Output Format

For each query operation, output one line containing one integer representing the corresponding answer.

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

1
2
2
1

Hint

For $40\%$ of the testdata, $n, q \le 5000$.

For all testdata, $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$.

Translated by ChatGPT 5