Binary Tree DFS Order Query

Given a binary tree with \(n\) nodes numbered from \(1\) to \(n\), with node \(1\) as the root. Initially, every node's value is \(-1\). The structure of the tree is defined as a complete binary tree: for any node \(i\), if \(2i \le n\) then node \(2i\) is its left child, and if \(2i+1 \le n\) then node \(2i+1\) is its right child.

You need to process \(q\) operations of two types:

1. Update: For given integers \(l, r, x\), assign the value \(x\) (where \(x \in \{-1, 0, 1\}\)) to every node with index in \([l, r]\).
2. Query: For a given node index \(i\), perform a DFS (depth-first search) traversal from the root with the following rule:
   • Visit the current node.
   • If the value of the current node is \(1\), traverse its right subtree first then its left subtree (if they exist).
   • Otherwise (if the value is \(-1\) or \(0\)), traverse its left subtree first then its right subtree (if they exist).
   Output the 1-indexed position of node \(i\) in this DFS order.

Output the result for every query (the second type of operation).

inputFormat

The first line contains two integers \(n\) and \(q\) separated by a space.

Each of the next \(q\) lines represents an operation in one of the following formats:

• For an update operation: 1 l r x (\(x\) is one of \(-1, 0, 1\)).
• For a query operation: 2 i.

outputFormat

For each query operation, output a single integer in a new line representing the position (1-indexed) of node \(i\) in the DFS order defined above.

sample

3 3
2 1
1 2 3 1
2 3

1
3