Domino Prediction

Interview

Time limit1sMemory limit256 MB

Summary
Given XORs of consecutive domino numbers, answer queries for the XOR of positions x and y, or for the value at y when x holds d.
Level

Medium6 of 10

Topics
Prefix sum, Bit manipulation, Array, Math
Solved
No attempts yet

Problem

Jeonggi works part-time at a board game cafe and enjoys playing dominoes behind his boss's back. Dominoes means lining up tiles and pushing one end so the others topple in a chain. Jeonggi uses the number dominoes his boss treasures most, so he tries hard not to get caught.

One day, while he is playing with the dominoes and watching them fall, captivated, he gets caught.

About to scold Jeonggi for taking his number dominoes, the boss sees the fallen number dominoes lined up perfectly and offers to let the matter slide if Jeonggi answers all his questions. He then explains how the number dominoes are really meant to be used.

Each number domino Jeonggi used has the same integer written on its front and back. Playing with number dominoes means using these numbers to guess the numbers on the dominoes.

The first domino falls and covers the second, the second covers the third, and so on: the i-th domino covers the (i+1)-th. The questioner records, for each domino from the first to the one just before the last, the XOR of that domino's number and the number on the domino it covered. That is, the XOR of the first domino's number and the second's, the XOR of the second's and the third's, and so on, for N-1 values in total.

After clearing away the fallen dominoes, the questioner shows the player the recorded numbers and asks two kinds of questions.

  1. Answer the XOR of the number on domino x and the number on domino y.
  2. Given that the number on domino x is d, answer the number on domino y.

Write a program that answers the boss's questions for Jeonggi, who is new to number dominoes.

Input

The first line gives the number of number dominoes N and the number of questions Q as integers. (3 ≤ N ≤ 2 × 105, 1 ≤ Q ≤ 105)

The second line gives the N-1 integers the boss recorded. (Each integer is between 0 and 231-1 inclusive.)

Starting from the third line, Q lines follow, one question per line. Each question has the form "0 x y" or "1 x y d", meaning question type 1 and type 2 respectively. (1 ≤ x ≤ y ≤ N, 0 ≤ d ≤ 231-1)

Output

Print the answers to the questions over Q lines.

Examples1

  1. Example 1

    Input
    5 5
1 2 3 4
0 1 2
0 1 3
1 1 2 3
1 3 5 5
0 1 1
    Expected output
    1
3
2
2
0