Problem Description

You need to include the header file lib.h.

When compiling locally, you need to compile together with lib.cpp.

The interactive library provides the following data type and functions:

struct Data{
	unsigned short a,b,c,d;
	void operator*=(const Data &x);
	void clr();
};

The Data type is a monoid $(D,*,e)$. Specifically:

$D$ is the set consisting of elements of type Data.

$*:D\times D\to D$.

$e\in D$.

$\forall x,y,z\in D, x*(y*z)=(x*y)*z$.

$\forall x\in D, x*e=e*x=x$.

Using x.clr() can modify $x$ to $e$.

Using x=y can modify $x$ to $y$.

Using x*=y can modify $x$ to $x*y$. The number of calls to this operation has a constant upper limit of $2\times 10^7$, not counting the cases where $x=e$ or $y=e$.

Initially, every point $(x,y)$ on the plane corresponds to a weight $d(x,y)\in D$.

You need to implement the following functions:

void update(int x,int dim,Data d1,Data d2);

Perform the following operation for every $(x_0,y_0)$:

If $dim=0$ and $x_0<x$, then modify $d(x_0,y_0)$ to $d(x_0,y_0)*d1$.

If $dim=0$ and $x_0\ge x$, then modify $d(x_0,y_0)$ to $d(x_0,y_0)*d2$.

If $dim=1$ and $y_0<x$, then modify $d(x_0,y_0)$ to $d(x_0,y_0)*d1$.

If $dim=1$ and $y_0\ge x$, then modify $d(x_0,y_0)$ to $d(x_0,y_0)*d2$.

Data query(int x,int y);

Query $d(x,y)$. The return value is the answer.

For your convenience, a template is provided here. Please complete the following code:

/* BEGIN HEADER: */
struct Data{
	unsigned short a,b,c,d;
	void operator*=(const Data &x);
	void clr();
};
void update(int x,int dim,Data d1,Data d2);
Data query(int x,int y);
/* END HEADER. */

#include <bits/stdc++.h>

void update(int x,int dim,Data d1,Data d2){
	// complete this
}
Data query(int x,int y){
	// complete this
}

Because Luogu’s interactive method is rather strange, when submitting you need to copy your local code here, put it inside the update and query functions, and submit it together with the HEADER above. When submitting, do not include the "lib.h" header file.

Input Format

This is an interactive problem, so this is not needed.

Output Format

This is an interactive problem, so this is not needed.

10
2 200842854 123159544
2 192001936 902183645
2 996055655 154684468
2 957446126 232761122
1 739061119 1 4 6
1 762263616 1 5 8
1 669159682 0 10 7
2 361701640 274578757
1 392040275 0 2 8
1 800311125 1 3 2

(0,0,0,0)
(0,0,0,0)
(0,0,0,0)
(0,0,0,0)
(19,19,329,10)

Hint

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

For the first 8 test groups, the numbers of operations are $10,1000,10000,20000,40000,60000,80000,10^5$, and $x,y,dim$ are chosen uniformly at random.

For the remaining testdata, the number of operations is $10^5$, and they form subtasks.

For all testdata:

For update operations, $1\le x\le 10^9$ and $dim\in\{0,1\}$.

For query operations, $1\le x,y\le 10^9$.

Translated by ChatGPT 5