Problem Background

2019/12/27 Updated the data range for the last point.

Steve leads his army to the stronghold of the dark forces.

However, he discovers that the dark forces are using crystals to protect themselves.

To break through the defense, Steve begins attacking the crystals with his weapons.

Problem Description

The dark forces' crystals are arranged in a row, and there are many of them.

The crystals can be divided into $n$ groups, with the $i$-th group containing $a_i$ crystals, each with a defense power of $na_i$.

Steve's weapons are also arranged in a row, and there are many of them.

The weapons can be divided into $n$ groups, with the $i$-th group containing $b_i$ weapons, each with an attack power of $nb_i$.

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

If the weapon's attack power is greater than the crystal's defense power, the attack is effective.

However, there are too many crystals and weapons, and Steve finds it difficult to determine which crystal and weapon are chosen.

Now Steve wants to know:

1. For all possible scenarios, how many ways can an effective attack be made?

2. If it is known that the chosen crystal's defense power is between the defense powers of the $x$-th and $y$-th groups of crystals, and the chosen weapon's attack power is between the attack powers of the $z$-th and $u$-th groups of weapons, then how many ways can an effective attack be made?

That is, the chosen crystal's defense power is not less than the smaller value and not greater than the larger value of the $x$-th and $y$-th groups of crystals' defense powers, and the same applies to the weapon.

Two ways are considered different if and only if the chosen crystal or weapon is different (can be within the same group).

Due to the urgency of the situation, you need to answer the questions quickly to help Steve make decisions for the next round of attacks.

Therefore, some test cases are forced to be online.

To avoid excessively large answers, the answer is taken modulo $998244353$.

Input Output Format

Input Format

Due to the large input/output size, use the following template to complete data generation. Refer to the template and examples for specific formats.

During evaluation, all test cases will only input 5 numbers and output 1 number, so you do not need input/output optimization.

For debugging convenience, this template can manually specify data and output the answer for each query by setting $k=0$.

For all test cases, the time consumed by the interaction library is guaranteed to be no more than 300ms.

#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);
                s=s*19260817+1;
                na[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);
                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);
            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;
            }
        }
    }
    void stop(){
        if(k>=2){write(res);putchar('\n');}
    }
}
int main(){
    lib::init();
    lib::reply(233);
    for(int i=1;i<=q;i++){
        lib::query();
        lib::reply(233);
    }
    lib::stop();
}

Output Format

If $k=0$, the answers to each query will be output separately.

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

Sample Input and Output

Sample Input #1

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

Sample Output #1

18
2
6
4
2
18
16
0
12
12

Sample Input #2

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

Sample Output #2

11
2
5
3
2
11
9
0
6
6

Sample Input #3

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

Sample Output #3

11
0
6
5
6
5
0
6

Sample Input #4

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

Sample Output #4

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

Sample Input #5

3 2 233 5 10

Sample Output #5

15618218285282996994

Sample Input #6

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

Sample Output #6

988687952
712318441
204869162
71500349
703342331
285345621
783818790
712318441
712318441
276369511
703342331

Notes

Sample 1 Explanation:

When choosing the second group of weapons, an effective attack can always be made.

When choosing the first group of weapons, an effective attack can only be made by choosing the first group of crystals.

Therefore, it is not difficult to find the answers to each query.

It is recommended to further understand the problem based on the examples.

Sample 5 is consistent with Sample 6.

Data Range:

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

Unless otherwise specified, $k=3$, i.e., data is generated by the template and forced to be online.

If $k=2$, the data is still generated by the generator but not forced to be online, meaning you can obtain the true value of the next query without answering the current one, and then answer in order.

见题面 Input 部分

见题面 Output 部分