Description

The dark forces’ crystals have been lined up in a row, and there are many of them.

The crystals can be divided into $n$ groups. The $i$-th group contains $a_i$ crystals, and their defense value is $na_i$.

Steve’s weapons have also been lined up in a row, and there are many of them.

The weapons can also be divided into $n$ groups. The $i$-th group contains $b_i$ weapons, and their attack value is $nb_i$.

In each round of attack, the dark forces will choose one crystal, and Steve will choose one weapon.

If the weapon’s attack value is greater than the crystal’s defense value, then this attack is effective.

However, there are too many crystals and weapons, so it is hard for Steve to know exactly which crystal and which weapon were chosen.

Now Steve wants to know:

1. For all possible situations, how many ways of choosing result in an effective attack.

2. If it is already known that the chosen crystal’s defense value is between the defense values of the crystals in group $x$ and group $y$, and the chosen weapon’s attack value is between the attack values of the weapons in group $z$ and group $u$, then how many ways of choosing result in an effective attack.

That is, the chosen crystal’s defense value is not less than the smaller of the defense values of group $x$ and group $y$, and not greater than the larger of them; similarly for the weapon.

Two choices are different if and only if the chosen crystal or the chosen weapon is different (they may be in the same group).

Since the battle is urgent, you need to answer the questions quickly so that Steve can decide the next round of attacks.

Therefore, some test points require online answering.

To avoid the answer being too large, take the answer modulo $998244353$.

Input Format

Because the input/output size is large, use the following template to generate the data. For the exact format, see the template and samples.

During judging, all test points will only input 5 numbers and output 1 number, so you do not need to optimize input/output.

For easier debugging, this template can manually specify the data and output the answer to each query; in that case you only need to input $k=0$.

For all test points, it is guaranteed that the time consumed by calling the interaction library does not exceed 300 ms.

#include<cstdio>
using namespace std;
#define u32 unsigned int
#define u64 unsigned long long
int cl;
const int N=2500007;
const long long M=998244353LL;
int n,q,k;
int a[N],na[N],b[N],nb[N];
int x,y,z,u;
namespace lib{
    u64 read(){
        u64 n=0;
        char c=getchar();
        while(c<'0'||c>'9')c=getchar();
        while(c>='0'&&c<='9'){
            n=n*10+c-'0';
            c=getchar();
        }
        return n;
    }
    char r[30];
    void write(u64 num){
        if(num==0){
            putchar('0');
            return;
        }
        int t=0;
        while(num){
            r[t++]=num%10+'0';
            num/=10;
        }
        while(t)putchar(r[--t]);
    }
    u64 s;
    u64 rand(u64 l,u64 r){
        s=s*19260817+1;
        return ((s>>8)%(r-l+1)+l);
    }
    int ra,t;
    void init(){
        n=read();k=read();
        if(k<2){
            for(int i=1;i<=n;i++){
                a[i]=read();na[i]=read();
            }
            for(int i=1;i<=n;i++){
                b[i]=read();nb[i]=read();
            }
        }else{
            s=read();ra=read();
            u64 bacs=s;
            for(int i=1;i<=n;i++){
            	s=s*19260817+1;
        		a[i]=((s>>8)%ra+1);
                //a[i]=rand(1,ra);
                s=s*19260817+1;
        		//na[i]=((s>>8)%(M-1)+1);
                //na[i]=rand(1,M-1);
            }
            s=bacs;
            for(int i=1;i<=n;i++){
            	s=s*19260817+1;
        		//a[i]=((s>>8)%ra+1);
                //a[i]=rand(1,ra);
                s=s*19260817+1;
        		na[i]=((s>>8)%(M-1)+1);
                //na[i]=rand(1,M-1);
            }
            bacs=s;
            for(int i=1;i<=n;i++){
                s=s*19260817+1;
        		b[i]=((s>>8)%ra+1);
                //a[i]=rand(1,ra);
                s=s*19260817+1;
        		//nb[i]=((s>>8)%(M-1)+1);
            }
            s=bacs;
            for(int i=1;i<=n;i++){
                s=s*19260817+1;
        		//b[i]=((s>>8)%ra+1);
                //a[i]=rand(1,ra);
                s=s*19260817+1;
        		nb[i]=((s>>8)%(M-1)+1);
            }
        }
        q=read();
    }
    u64 lastans;
    u64 res;
    void reply(u64 num){
        if(k<2){
            write(num);putchar('\n');
        }else{
            res=res*233+num;
        }
        lastans^=num;
    }
    void query(){
        if(k<2){
            x=read();y=read();z=read();u=read();
        }else{
        	s=s*19260817+1;
        	x=((s>>8)%n+1);
        	s=s*19260817+1;
        	y=((s>>8)%n+1);
        	s=s*19260817+1;
        	z=((s>>8)%n+1);
        	s=s*19260817+1;
        	u=((s>>8)%n+1);
            //x=rand(1,n);y=rand(1,n);z=rand(1,n);u=rand(1,n);
        }
        if(k&1){
        	int t=lastans%n+1;
        	if((x+=t)>n)x-=n;
        	if((y+=t)>n)y-=n;
        	if((z+=t)>n)z-=n;
        	if((u+=t)>n)u-=n;
            /*x=(x+lastans)%n+1;
            y=(y+lastans)%n+1;
            z=(z+lastans)%n+1;
            u=(u+lastans)%n+1;*/
        }
    }
    void stop(){
        if(k>=2){write(res);putchar('\n');}
    }
}
int main(){
	lib::init();
	//现在你可以使用生成的a,na,b,nb
	
    //回答第一问
    
	lib::reply(233);
	
	for(int i=1;i<=q;i++){
		lib::query();
		
		//回答第二问 
        
		lib::reply(233);
	}
	lib::stop();
}

Output Format

If $k=0$, the answer to each question will be output separately.

Otherwise, only one integer will be output to check whether the result is correct.

2 0
1 1
3 3
2 2
4 4
9
1 1 1 1
1 1 1 2
1 1 2 2
2 1 1 1
1 2 1 2
1 2 2 2
2 2 1 1
2 2 1 2
2 2 2 2

18
2
6
4
2
18
16
0
12
12

2 0
1 1
2 2
2 2
3 3
9
1 1 1 1
1 1 1 2
1 1 2 2
1 2 1 1
1 2 1 2
1 2 2 2
2 2 1 1
2 2 1 2
2 2 2 2

11
2
5
3
2
11
9
0
6
6

5 0
1 1
1 1
1 1
2 1
2 1
1 1
1 1
2 1
2 1
3 1
7
2 4 1 1
1 3 3 4
3 4 5 5
2 5 4 4
1 5 5 5
1 3 1 2
1 2 3 4

11
0
6
5
6
5
0
6

3 0
3 1
2 2
1 3
4 4
5 5
6 6
12
1 3 2 2
1 2 2 3
3 1 1 2
2 1 3 1
1 1 2 3
3 1 3 1
3 2 2 3
1 2 3 3
1 2 1 3
3 2 1 1
2 2 1 3
3 3 1 2

90
30
33
54
45
11
90
55
18
45
20
30
27

3 2 233 5 10

15618218285282996994

3 0
3 754517792
1 842082509
4 600944080
2 592435186
5 348652025
5 247250863
10
1 3 3 2
3 2 1 1
2 2 3 2
2 1 2 1
3 3 3 1
2 3 3 2
1 3 3 3
1 3 3 3
2 2 1 3
2 1 2 1

988687952
712318441
204869162
71500349
703342331
285345621
783818790
712318441
712318441
276369511
703342331

Hint

Explanation for Sample 1:

When choosing the weapons in the second group, you can always make an effective attack.

When choosing the weapons in the first group, only choosing the crystals in the first group can make an effective attack.

Therefore, it is not hard to find the answer to each question.

It is recommended to further understand the statement based on the samples.

Sample 5 is the same as Sample 6.

Constraints:

For all data, $1 \le x,y,z,u \le n$, $1 \le a_i,b_i \le 10^9$, and $1 \le na_i,nb_i \le 998244352$.

Unless otherwise specified, $k=3$, i.e., the data is generated by the template and online answering is required.

If $k=2$, the data is still generated by the generator, but online answering is not required. That is, you can get the real value of the next query without answering the current query, and then answer them in order afterward.

Translated by ChatGPT 5