Priyansh Saxena aka Baba is taking part in the very first edition of KPL (Kamand Premier League) as a team leader. He has 5 bhakts in his team. Before the starting of the KPL rounds, all the team leaders are given a small task. But because Baba has to go to Dalhousie on the day itself after the auction, he asks all his bhatks to solve the task for him. You are one of them and if you want to participate in the KPL rounds, you must have to solve the task.

There are N coins arranged in a row. Each showing either a Head or a Tail (A Head is represented by 1 and a Tail by 0). There are two types of queries:

• 1 K - flip the Kth coin (i.e. from Head to Tail and vice-versa)

• 2 L R – tell the total number of contiguous sets of Heads between L and R (both inclusive).

(Note : The array is 1-indexed)

Input

• The first line of the input contains two space-separated integers N and Q.

• The second line contains N space-separated integers A₁, A₂,... ,A_n.

• Q line follows. Each of these lines describes one query in the following format:

  • 1 K for a query of the first type.

  • 2 L R for a query of the second type.

Output

For each query of the second type, print a single line containing one integer – The total number of sets of contiguous heads between L and R (both inclusive).

Constraints

• 1 <= N,Q <= 10⁵

• 0 <= A_i <= 1 for each valid i

• 1 <= L <= R <= N

• 1 <= K <= N

Subtasks

Subtask #1 (20 points):

• 1 <= N,Q <= 10³

Subtask #2 (80 points):

• Original Constraints