Background

Problem Description

Given a monoid with identity $(D,+,e)$, and a sequence $a_1,\dots,a_n$ consisting of elements in $D$, with all initial values being $e$, you need to support $m$ operations. Each operation is either a point update or a range sum query.

For each update operation, the number of times you use $+$ must not exceed $M_1$.

For each query operation, the number of times you use $+$ must not exceed $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 lib.h, or put its content at the very beginning of your program.

The content of the provided header lib.h is:

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 of these parts.

You need to implement:

init, used for initialization. Here n,k,d represent $n,M_2$, and the identity element $e$ of $D$, respectively. You may use $+$, but since $e+e=e$, you cannot obtain useful results from it.

update, which represents an update operation, setting $a_x$ to $d$.

query, which represents a range sum query operation, querying $a_l+a_{l+1}+\dots+a_r$. The query result should be returned as the return value.

Hint

Idea: ccz181078, Solution: ccz181078, Code: ccz181078, Data: ccz181078.

For all testdata, $n=10^5,\;m=2\times 10^5$.

Constraints

The lib\down directory contains the provided interactive library files.

The lib\require directory contains the interactive library files used for judging.

The data directory contains the judging test points.

The data2 directory contains the provided samples.

Translated by ChatGPT 5