Binary Tree Navigation

You are given an infinite binary tree where each node has two children and each node (except the root) has a parent. The tree is numbered as follows: the root node is numbered \(1\), and for any node numbered \(i\), its left child is \(2 \times i\) and its right child is \(2 \times i+1\).

You are provided with a starting node \(s\) and a sequence of \(n\) moves. Each move is one of the following three types:

• Move Type 1: If the current node has a parent, move to the parent node; if the current node is the root (i.e. \(1\)), remain in the same position.
• Move Type 2: Move to the left child of the current node.
• Move Type 3: Move to the right child of the current node.

Your task is to determine the final node number after performing all \(n\) moves. It is guaranteed that the final node number does not exceed \(10^{12}\).

inputFormat

The input consists of two lines.

The first line contains two integers \(s\) and \(n\) (\(1 \le s \le 10^{12}\), \(n \ge 1\)), where \(s\) is the starting node number and \(n\) is the number of moves.

The second line contains \(n\) space-separated integers. Each integer is one of the three movement types: 1, 2, or 3.

outputFormat

Output a single integer representing the node number after performing all \(n\) moves.

sample

1 3
2 3 1

2