题目描述

你需要包含头文件lib.h；

在本地编译时，需要和 lib.cpp 一起编译；

交互库提供了以下数据类型和函数：

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

Data 类型是一个含幺半群 $(D,*,e)$，具体地：

$D$ 是类型为 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$

使用 x.clr() 可以将 $x$ 修改为 $e$；

使用 x=y 可以将 $x$ 修改为 $y$；

使用 x*=y 可以将 $x$ 修改为 $x*y$，这个操作的调用次数有常数上限 $2\times 10^7$，不计 $x=e$ 或 $y=e$ 的情况。

初始条件下，平面上每个点 $(x,y)$ 都对应一个权值 $d(x,y)\in D$；

你需要实现以下函数：

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

对每个 $(x_0,y_0)$ 执行操作：

若 $dim=0$ 且 $x_0<x$，则将 $d(x_0,y_0)$ 修改为 $d(x_0,y_0)*d1$；

若 $dim=0$ 且 $x_0\ge x$，则将 $d(x_0,y_0)$ 修改为 $d(x_0,y_0)*d2$；

若 $dim=1$ 且 $y_0<x$，则将 $d(x_0,y_0)$ 修改为 $d(x_0,y_0)*d1$；

若 $dim=1$ 且 $y_0\ge x$，则将 $d(x_0,y_0)$ 修改为 $d(x_0,y_0)*d2$；

Data query(int x,int y);

查询 $d(x,y)$，返回值为答案。

为了您的方便，这里提供模板。请完善以下代码：

/* 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
}

由于洛谷的交互方法比较奇怪，所以提交的时候需要把本地的代码复制过来，放在 update, query 函数这里，和前面的 HEADER 一起提交。提交时不引用 "lib.h" 头文件。

输入格式

这是交互题，不需要这种东西。

输出格式

这是交互题，不需要这种东西。

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)

提示

Idea：ccz181078，Solution：ccz181078，Code：ccz181078，Data：ccz181078

对于前 8 组数据，操作个数分别为 $10,1000,10000,20000,40000,60000,80000,10^5$，且 $x,y,dim$ 均匀随机选取；

对于其余数据，操作个数为 $10^5$，且构成子任务。

对于所有数据： 对于 update 操作，满足 $1\le x\le 10^9$，$dim\in\{0,1\}$； 对于 query 操作，满足 $1\le x,y\le 10^9$。