Binary Tree Color Updates

You are given a complete binary tree with \(n\) nodes, numbered from 1 to \(n\). The tree is defined as follows: for each node \(i\), its left child is \(2i\) (if \(2i \le n\)) and its right child is \(2i+1\) (if \(2i+1 \le n\)). Initially, each node is colored 0.

You will be given \(q\) operations. Each operation is one of the following types:

• Update operation: x y z. This means that for the given node \(x\), all nodes whose distance from node \(x\) is at most \(y\) (i.e. all nodes \(v\) satisfying \(d(x,v) \le y\)) will have their color changed to \(z\). The distance between two nodes is defined as the number of edges on the shortest path connecting them.
• Query operation: x. This means you should output the current color of node \(x\).

Note: The operations occur sequentially and previous operations may affect later queries.

inputFormat

The first line contains two integers \(n\) and \(q\) (the number of nodes and the number of operations).

The following \(q\) lines each represent an operation. An operation is given in one of the following formats:

• x y z — update operation (update the colors of all nodes within distance \(y\) from node \(x\) to \(z\)).
• x — query operation (output the color of node \(x\)).

outputFormat

For each query operation, output one integer on a new line indicating the current color of the queried node.

sample

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

5
8
5
0