Interactive Monoid Range Query

You are given a monoid \( (D,+,e) \) where e is the identity element and the binary operation \( + \) satisfies:

• \( e + a = a + e = a \) for any \( a \in D \)
• \( (a+b)+c = a+(b+c) \) for any \( a,b,c \in D \)

There is a sequence of \( n \) elements \( a_1, a_2, \dots, a_n \) from \( D \), all initially set to e. You need to support m operations. Each operation is one of the following:

• Update Operation: Change the element at a given index \( x \) to a new element \( d \) from \( D \). (Note: Each update operation is allowed to use \( + \) at most \( M_1 \) times.)
• Query Operation: Compute the range sum \( a_l + a_{l+1} + \cdots + a_r \). (Note: Each query operation is allowed to use \( + \) at most \( M_2 \) times.)

This is an interactive problem. You are provided with a header file lib.h whose content is given below. You must include this header (or paste its contents at the beginning of your program) and then implement the following functions:

// The provided header: lib.h
struct Data {
    unsigned short a, b, c, d;
};

Data operator+(Data a, Data b);

void init(int n, int k, Data d);
void update(int x, Data d);
Data query(int l, int r);

Here, Data represents an element of \( D \), and operator+ implements the binary operation \( + \). The function init is called once at the beginning with parameters n, k (which represents \( M_2 \)), and d (the identity element e). Then you will receive m operations. For an update operation, you must update a_x to the given d by calling update. For a query operation, you must compute the sum over the range \([l, r]\) by implementing query and output the result accordingly.

inputFormat

The input begins with a line containing four integers:

1. \( n \): the number of elements.
2. \( m \): the number of operations.
3. \( M_1 \): the maximum number of uses of \( + \) allowed in each update (not used directly in your implementation).
4. \( M_2 \): the maximum number of uses of \( + \) allowed in each query.

The next line contains four non-negative integers representing the identity element e (i.e. the values of a, b, c, and d in Data). It is guaranteed that for the given monoid, e + e = e.

Then follow m lines, each representing an operation. There are two kinds of operations:

• If the operation is an update, the line begins with 1 followed by an integer x (the index to update, 1-indexed) and four integers representing the new Data value.
• If the operation is a query, the line begins with 2 followed by two integers l and r indicating the range \([l, r]\) to query.

outputFormat

For each query operation, output a line with four integers corresponding to the fields of the resulting Data (in the order a b c d), separated by spaces.

sample

5 5 10 10
0 0 0 0
2 1 5
1 2 1 2 3 4
2 1 3
1 5 5 5 5 5
2 2 5

0 0 0 0
1 2 3 4
6 7 8 9

</p>