Algorithms and Data Structures

Range XOR Queries

You are given an array of n elements and q queries. There are two types of queries:
  1. Get the XOR (exclusive OR) of the given range
  1. 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:
  1. 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.
  1. 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.

Examples

Input
Output
6 4 1 4 2 7 5 3 1 1 3 2 2 9 1 2 5 1 3 6
7 9 3

Constraints

Time limit: 0.6 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue