Given a monoid $(D,+,e)$ and a sequence $a_1, \dots, a_n$ of elements in $D$, all initially set to $e$, support $m$ operations, where each operation is either a point update or a range sum query.

The number of times the $+$ operation is used in each update is limited to at most $M_1$.

The number of times the $+$ operation is used in each query is limited to at most $M_2$.

Basic properties of the monoid:

$\forall a\in D,\; e+a=a+e=a$

$\forall a,b,c\in D,\;(a+b)+c=a+(b+c)$

This is an interactive problem. You need to include the header file lib.h or place its content at the beginning of your program.

The content of the provided header file lib.h is as follows:

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 $D$, and Data operator+ represents $+$. The interactive library provides the implementation for these.

You need to implement:

init: Used for initialization. $n, k, d$ represent $n, M_2$, and the identity element $e$ of $D$, respectively. You may use $+$, but since $e+e=e$, it cannot yield useful results.

update: Represents an update operation, changing $a_x$ to $d$.

query: Represents a range sum query, calculating $a_l+a_{l+1}+\dots+a_r$. The result of the query should be returned.

Subtasks

For all test cases, $n=10^5$ and $m=2\times 10^5$.