## Double Doors Regional P5 - Tudor Eats Ice Cream Cones

View as PDF

Points: 15
Time limit: 1.4s
Java 2.75s
Memory limit: 256M

Problem type

Tudor likes ice cream cones!

One day, Tudor travels to an ice cream convention to eat ice cream. There are stands, numbered through . Stand is serving flavor .

Each of the stands charges a certain price for ice cream, which Tudor interprets as a signal of the quality of the ice cream. Tudor has strong flavor preferences and will decide to order ice cream from two stands within certain flavor constraints, choosing to either order from the two stands with the highest price, in the event he wishes to try some gourmet ice cream, or the two stands with the lowest price, in the event he wishes to save on money.

As the convention goes on, stands may change their prices. Tudor's flavor preferences may also change. Help Tudor eat ice cream!

#### Input Specification

The first line contains two positive integers, and . You may assume and are no larger than . Furthermore, will be a perfect square and will not be equal to 1.

The next line contains positive integers, the costs of each of the stands in order. No stand will exceed in cost.

Each of the next lines will contain three integers. The first integer in each line will be either , , or . The remaining integers on the line will be encoded. All encoded integers should be decoded by XOR'ing them with the answer of the most recent query. In the event there were no prior answers, XOR the encoded integers with .

If the first integer in the line is 1, the next two integers are and , indicating that stand should have value . The decoded value will satisfy . The decoded value will satisfy .

If the first integer in the line is 2, the next two integers are and , indicating that Tudor wishes to know the sum of the prices of the two cheapest stands that offer a flavor between and . The decoded values and will satisfy .

If the first integer in the line is 3, the next two integers are and , indicating that Tudor wishes to know the sum of the prices of the two most expensive stands that offer a flavor between and . The decoded values and will satisfy .

#### Output Specification

For each query, output the desired cost on a separate line.

#### Sample Input

4 4
1 4 2 5
2 1 1
2 7 7
1 3 6
3 6 5

#### Sample Output

5
7
6