You are given an array of n elements and q queries. There are two types of queries:

Get the XOR (exclusive OR) of the given range

Update the array at the given location

Your task is to process the queries efficiently.

Input

The first line of the input contains two integers n and q (1 β€ n, q β€ 100 000), representing the number of elements in the array and the number of queries, respectively.

The second line contains n space-separated integers (), representing the initial elements of the array.

The following q lines each represent a query:

For range XOR queries: The line starts with the number 1 followed by two integers and (), representing the range of indices [] for which the XOR value needs to be calculated.

For array update queries: The line starts with the number 2 followed by two integers and (), representing the position of the element to be updated and its new value.

Output

For each range XOR query, print the XOR value of the elements within the given range on a separate line.