Jusuf's Card Battle Simulation

Jusuf has N cards numbered from 1 to N where the i-th card has a power p_i. He will perform Q operations which are of two types:

• 1 i r: Update the card at position i so that its power becomes r (i.e. set p_i = r).
• 2 l k: Simulate a battle using 2^k consecutive cards starting from index l (cards p_l, p_l+1, …, p_l+2^k-1). The battle consists of k rounds. In each round, the cards are paired consecutively: the first and second cards form a pair, the third and fourth cards form another pair, and so on. For a pair with powers A and B, the card with the higher power wins and its power is updated to \(|A - B|\); the other card is eliminated. If \(A = B\), the outcome is considered ambiguous and one card is chosen randomly to win, with its power becoming 0. After k rounds, only one card remains. The task is to output the final power of the remaining card.</p>

  Note that these operations do not affect the original card deck outside the operation. That is, update operations actually change the deck, but battle simulations are done on temporary copies of the cards.

  inputFormat

  The first line contains two integers, N and Q (1 ≤ N, Q). The second line contains N integers: p₁, p₂, …, p_N, representing the initial power of each card.

  Each of the following Q lines represents an operation in one of the following formats:

  • 1 i r — update operation: set p_i to r.
  • 2 l k — simulation operation: simulate a battle on the subarray starting at index l with length 2^k.

  outputFormat

  For each simulation operation (type 2), output the final remaining card's power on a new line.

  sample

  5 5
  5 7 1 3 9
  2 1 2
  1 3 10
  2 2 2
  2 1 1
  1 5 4

  0
  3
  2

  </p>