Mars Mall Shopping

On Mars, a commercial street is lined with shops numbered from 1 to \(n\). Each shop sells a variety of products, each priced with a non-negative integer \(v\). Every day, a shop may receive new products (possibly with a duplicate price), and in addition, every shop always offers a special product (with price 0) that is available regardless of its stocking date.

A Martian shopper visits a contiguous segment of shops, say shops in the interval \([l, r]\), and selects the product they like the most. Each Martian has a personal preference key \(x\). For any product priced \(v\), the Martian’s preference is quantified by \(v \oplus x\) (i.e. the bitwise XOR of \(v\) and \(x\)); the larger the value, the more the Martian likes that product.

However, the shopping card only permits the purchase of products that have been stocked during the most recent \(d\) days (including the current day), with the exception of the special product which is always available.

You are given \(q\) events in chronological order (each event happens on a new day). The events are in one of the following two formats:

• 0 s v: On that day, shop number \(s\) receives a new product with price \(v\).
• 1 l r x d: A Martian with preference key \(x\) shops at all shops between \(l\) and \(r\) inclusive, considering only the products stocked in the last \(d\) days (i.e. products stocked on a day \(\geq T-d+1\), where \(T\) is the current day). In addition, each shop always offers a special product with price 0. Output the maximum value of \(v \oplus x\) the Martian can achieve.

Note: Assume that each event occurs on a new day. For queries, products stocked earlier than \(T-d+1\) are not considered, except for the special product.

inputFormat

The first line contains two integers (n) and (q), where (n) is the number of shops and (q) is the number of events. Each of the following (q) lines contains an event in one of the following formats:

0 s v

1 l r x d

For an event of type 0, (s) ((1 \le s \le n)) is the shop number and (v) ((0 \le v)) is the price of a new product stocked on that day.

For an event of type 1, (l) and (r) define the range of shops ((1 \le l \le r \le n)), (x) is the Martian's preference key, and (d) is the number of recent days (including the current day) from which products can be selected.

outputFormat

For each event of type 1, output a single line containing the maximum value of (v \oplus x) that can be achieved from the available products in shops ([l, r]), considering only those products stocked within the last (d) days and the special product (which has a fixed price of 0).

sample

3 5
0 1 5
0 2 7
1 1 2 3 2
0 2 9
1 1 3 8 3

4
8