In his first flashback, Bai Yuechu recalls the story of Wangquan Fuqui:

Wangquan Fuqui is a legendary demon slayer! So legendary that demons will fight each other for the honor to face him. However, what they do not know is that Fuqui's skill comes not only from his blade, but his ability to analyze a demon's abilities. Fuqui secretly has a collection of the strengths and weaknesses of every type of demon.

The ~2^N~ (~N \le 16~) demons, numbered from ~0~ to ~N-1~, that seek to challenge Fuqui today are arranged in a tournament bracket. In each round of the tournament, demons ~2i~ and ~2i+1~ fight each other to the death for each ~i \le N/2~ and the winner advances to the next round. The winner of ~(2i, 2i+1)~ is placed in the index ~i~ for the next round, and the process repeats. When there is only one demon remaining, it is selected to face Wangquan Fuqui in the final match.

Wangquan Fuqui knows the type of each demon in the tournament. However, he would like to be prepared as early as possible and wishes to know the earliest possible round in which he could be certain of the type of demon he will face, among all possible combinations of wins and losses in the tournament. See the explanation of the sample for details.

However, some of the demons predicted his plan, and are planning to ingest magical type-changing potions before the tournament. However, Wangquan Fuqui is not so easily deterred. He has hired you to keep track of every change and report the answer to the aforementioned query after each change.

Input Specification

Line 1: Two integers, ~N~ and ~Q~ (~1 \le N \le 16, 1 \le Q \le 100\,000~).
Line 2: ~2^N~ integers, each less than ~10^9~, the type of the ~i~-th demon.
Next ~Q~ lines: Two integers each, ~p_i~ and ~x_i~, denoting that the demon at index ~p_i~ becomes type ~x_i~.

Sample Input 1

3 2
1 2 3 1 1 2 2 3
6 1
0 2

Sample Output 1

2
1
2

Sample Input 2

1 1
1 1
0 2

Sample Output 2

0
1

Explanation

Before any changes are made, the tournament bracket looks like this:

The above is a possible result after 2 rounds where the winner is guaranteed to be type 2. There are no results that require fewer rounds to guarantee the type of the winner.

After the first update, the bracket could become this:

After the first round, all remaining demons are type one. Therefore, the answer is 1. After the last change, this is no longer possible and the answer becomes 2.