## Description

## 1 Let us sort (40% of this assignment)

1.1 Description

Little X has a list A and a factor k. There are n positive integers in A. Little X wants to construct

some 2D points (xi

, yi) by assigning xi = ⌊

ai

k

⌋ and yi = ai%k, and he wants to sort these points in

several methods.

Method one, sort all points by the x-coordinates from smallest to largest, and for those with the same

x-coordinate, sort by the y-coordinates from smallest to largest.

Method two, sort all points by the x-coordinates from largest to smallest, and for those with the same

x-coordinate, sort by the y-coordinates from smallest to largest.

Method three, sort all elements ai by the x-coordinates from smallest to largest, and for those with

the same x-coordinate, sort by the y-coordinates from largest to smallest.

Method four, sort all elements ai by the x-coordinates from largest to smallest, and for those with the

same x-coordinate, sort by the y-coordinates from largest to smallest.

1.2 Input

Each test contains multiple test cases. The first line contains a single integer T(1 ≤ T ≤ 10) the

number of test cases. The description of the test cases follows.

The first line of each test case contains three integers n, k, id(1 ≤ n, k ≤ 105

, 1 ≤ id ≤ 4), separating

by one space, where n represents the length of the list and id represents the method Little X hopes

you to use.

The second line of each test case will be the list A (1 ≤ ai ≤ 109

).

The sum of n over all test cases in one test won’t exceed 5 × 105

.

1.3 Output

For each test case, output n lines, the ith line containing two integers xi

, yi

, separating by one space,

indicating the coordinate of the ith point of the constructed list sorted according to the given order.

The output of each test case is separated by one empty line.

Sample Input 1

4

2 65 1

7917 1292

1 41 1

6098

2 57 1

7920 4092

3 3 1

8596 1849 5806

Sample Output 1

19 57

121 52

148 30

71 45

138 54

616 1

1935 1

2865 1

There are four test cases in the example test, the first test case’s converted points list is [(121, 52),(19, 57)]

and Little X wants us to sort it according to the first method.

So the resulting list of the first test case is [(19, 57),(121, 52)]. The processes of the other test cases

are similar.

You can find more samples in the attached file on BB.

Problem Scale & Subtasks

There are 5 tests in total, with the same weight.

Test Case No. Constraints

1 1 ≤ n ≤ 5, id = 1.

2 1 ≤ n ≤ 100, 1 ≤ k ≤ 105

, 1 ≤ id ≤ 2

3 1 ≤ n ≤ 1000, 1 ≤ k ≤ 105

, 1 ≤ id ≤ 4

4 1 ≤ n ≤ 104

, 1 ≤ k ≤ 105

, 1 ≤ id ≤ 4

5 1 ≤ n ≤ 105

, 1 ≤ k ≤ 105

, 1 ≤ id ≤ 4

Hint

Try to define the relationship between the points by the requirement.

## 2 Detecting Tyranids (50% of this assignment)

2.1 Description

There is a galaxy map with n × m grids in it, and there are p Tyranid squads, each squad has k

Tyranids and is located in grid (i, j).

Suppose each grid (i, j) contains ki,j Tyranids. Now, as a commander of Space Marine, you want to

know the expected number of Tyranids in any rectangle on the map.

Formally speaking, you want to know the result of the following expression given the information of p

Tyranid squads.

Xn

a=1

Xm

b=1

Xn

c=a

Xm

d=b

Xc

i=a

X

d

j=b

ki,j

Note this number may be very large, you only need to output the remainder of the result mod

998244353.

2.2 Input

The first line contains 3 integers n, m, and p(1 ≤ n, m, p ≤ 105

).

For the following p lines, each line contains 3 integers i(1 ≤ i ≤ n), j(1 ≤ j ≤ m), and k(1 ≤ k ≤ 109

).

2.3 Output

One line contains one integer representing the remainder of the result mod 998244353.

Sample Input 1

4 3 1

2 1 1

Sample Output 1

For the first example, there is only one non-zero ki,j , k2,1 = 1.

Note that for n = 4, m = 3, there are 18 rectangles containing the grid (2, 1).

Figure 1: explanation of example 1

The orange portion has 6 grids and the blue area has 3, while 18 = 6 × 3.

Sample Input 2

5 5 5

3 4 2

4 5 6

4 4 2

2 3 1

3 4 3

Sample Output 2

800

For the second example, we can list every non-zero ki,j .

k2,3 = 1, k3,4 = 5, k4,4 = 2, k4,5 = 6. Then the target expression has a result of 800.

You can find more samples in the attached file on BB.

Problem Scale & Subtasks

There are 10 tests in total, with the same weight.

Test Case No. Constraints

1-3 1 ≤ n, m, p ≤ 10, 1 ≤ k ≤ 10

4-6 1 ≤ n, m, p ≤ 100, 1 ≤ k ≤ 100

7 1 ≤ n, m, p ≤ 105

, k = 1

8-10 1 ≤ n, m, p ≤ 105

, 1 ≤ k ≤ 109

Hint

For C/C++ and Java users, an int type stores integers range from -2,147,483,648 to 2,147,483,647. It

may be too small for this problem. You need other data types, such as long long for C/C++ and long

for Java. They store integers ranging from -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807.

Use scanf(“%lld”,&n) for C, cin>>n for C++ and n = scanner.nextLong() for Java to get the

input n. And the other operations for long and long long are quite same as int.

Consider the number of grids containing one Tyranid, then consider how to combine all these numbers.

Remember to take modular after doing any arithmetic operations.

For instance, make sure for any a = b + c, you write it as a = (b + c) mod 998244353.

2.4 Extension

What if we want to calculate the variance?