Theme NexT works best with JavaScript enabled

## A - String

### 题目描述

Gromah and LZR entered the great tomb, the first thing they see is a matrix of size $n \times m$ , and the elements in the matrix are all $0$ or $1$ .

LZR finds a note board saying “An all-one matrix is defined as the matrix whose elements are all $1$ , you should determine the number of all-one submatrices of the given matrix that are not completely included by any other all-one submatrices” .

Meanwhile, Gromah also finds a password lock, obviously the password should be the number mentioned in the note board!

### 输入描述

The first line contains two positive integers $n,m$ denoting the size of given matrix.

Following $n$ lines each contains a string with length $m$ ，whose elements are allor $0$ or $1$ ，denoting the given matrix.

$1\le n,m \le 3000$

### 输出描述

Print a non-negative integer, denoting the answer.

### 示例1

#### 说明

The $5$ matrices are $(1,2)-(1,4)$ , $(1,2)-(2,3)$ , $(1,2)-(3,2)$ , $(2,1)-(2,3)$ , $(3,4)-(3,4)$ .

## B - Beauty Values

### 题目描述

Gromah and LZR have entered the second level. There is a sequence $a_1, a_2, \cdots, a_n$ on the wall.

There is also a note board saying “the beauty value of a sequence is the number of different elements in the sequence”.

LZR soon comes up with the password of this level, which is the sum of the beauty values of all successive subintervals of the sequence on the wall.

### 输入描述

The first line contains one positive integer $n$ , denoting the length of the sequence.

The second line contains $n$ positive integers $a_1, a_2, \cdots, a_n$ , denoting the sequence.

$1 \le a_i \le n \le 10^5$

### 输出描述

Print a non-negative integer in a single line, denoting the answer.

### 示例1

#### 说明

The beauty values of subintervals $[1,1], [2,2], [3,3], [4,4]$ are all $1$ .

The beauty values of subintervals $[1,2], [1,3], [2,3], [3,4]$ are all $2$ .

The beauty values of subintervals $[1,4], [2,4]$ are all $3$ .

As a result, the sum of all beauty values are $1\times 4 + 2\times 4 + 3\times 2 = 18$ .

## C - CDMA

### 题目描述

Gromah and LZR have entered the third level. There is a blank grid of size $m \times m$ , and above the grid is a word “CDMA”.

In CDMA Technology, a Technology about computer network, every network node should be appointed a unique binary sequence with a fixed and the same length. Moreover, if we regard $0$ in the sequence as $-1$ , and regard $1$ as $+1$ , then these sequences should satisfy that for any two different sequences $s,t$ , the inner product of $s,t$ should be exactly $0$ .

The inner product of two sequences $s,t$ with the same length $n$ equals to $\sum_{i=1}^{n} s_it_i$ .

So, the key to the next level is to construct a grid of size $m\times m$ , whose elements are all $-1$ or $1$ , and for any two different rows, the inner product of them should be exactly $0$ .

In this problem, it is guaranteed that $m$ is a positive integer power of $2$ and there exists some solutions for input $m$ . If there are multiple solutions, you may print any of them.

### 输入描述

Only one positive integer $m$ in one line.

$m \in \{2^k \; | \;k = 1, 2, \cdots, 10\}$

### 输出描述

Print $m$ lines, each contains a sequence with length $m$ , whose elements should be all $-1$ or $1$ satisfying that for any two different rows, the inner product of them equals $0$ .

You may print multiple blank spaces between two numbers or at the end of each line, and you may print any number of blank characters at the end of whole output file.

### 示例1

#### 说明

The inner product of the two rows is $1\times(-1) + 1\times 1 = 0$ .

## D - Distance

### 题目描述

Gromah and LZR have entered the fourth level. There is a blank cube with size $n\times m\times h$ hanging on the wall.

Gromah soon finds a list beside the cube, there are $q$ instructions in the list and each instruction is in one of the following two formats:

1. $(1, x, y, z)$ , meaning to add a tag on position $(x, y, z)$ in the cube
2. $(2,x, y, z)$ , meaning to determine the minimum Manhattan Distance to the given position $(x, y, z)$ among all tagged positions

Manhattan Distance between two positions $(x_1, y_1, z_1), (x_2, y_2, z_2)$ is defined as $|x_1 - x_2| + |y_1 - y_2| + |z_1 - z_2|$ .

LZR also finds a note board saying that the password of this level is the sequence made up of all results of the instructions in format $2$ .

Please help them get all results of the instructions in format $2$ .

### 输入描述

The first line contains four positive integers $n,m,h,q$ , denoting the sizes in three dimensions of the cube and the number of instructions.

Following $q$ lines each contains four positive integers $op,x, y, z$ , where $op=1$ means to add a tag on $(x,y,z)$ while $op=2$ means to make a query on $(x,y,z)$ .

$1 \le n\times m\times h, q\le 10^5, 1 \le x \le n, 1 \le y \le m, 1 \le z \le h$

It is guaranteed that the first instruction is in format $1$ and that no position will be tagged more than once.

### 输出描述

For each instruction in format $2$ , output the answer in one line.

### 示例1

#### 说明

For the first query, there is only one tagged position $(1,1,1)$ currently, so the answer is $|1-2| + |1-3| + |1-3| = 5$ .

For the second query, $(3,1,1)$ is the nearest tagged position, so the answer is $|3-3| + |1-3| + |1-2| = 3$ .

## E - Explorer

### 题目描述

Gromah and LZR have entered the fifth level. Unlike the first four levels, they should do some moves in this level.

There are $n$ vertices and $m$ bidirectional roads in this level, each road is in format $(u, v, l, r)$ ,which means that vertex $u$ and $v$ are connected by this road, but the sizes of passers should be in interval $[l,r]$ . Since passers with small size are likely to be attacked by other animals and passers with large size may be blocked by some narrow roads.

Moreover, vertex $1$ is the starting point and vertex $n$ is the destination. Gromah and LZR should go from vertex $1$ to vertex $n$ to enter the next level.

At the beginning of their exploration, they may drink a magic potion to set their sizes to a fixed positive integer. They want to know the number of positive integer sizes that make it possible for them to go from $1$ to $n$ .

### 输入描述

The first line contains two positive integers $n,m$ , denoting the number of vertices and roads.

Following m lines each contains four positive integers $u, v, l, r$ , denoting a bidirectional road $(u, v, l, r)$ .

$1 \le n,m \le 10^5, 1 \le u < v \le n, 1 \le l \le r \le 10^9$

### 输出描述

Print a non-negative integer in a single line, denoting the number of valid sizes.

### 示例1

#### 说明

There are $2$ valid sizes : $2$ and $3$ .

For size $2$ , there exists a path $1 \rightarrow 2 \rightarrow 3 \rightarrow 5$ .

For size $3$ , there exists a path $1 \rightarrow 2 \rightarrow 4 \rightarrow 5$ .

## F - Flower Dance

### 题目描述

Gromah and LZR have entered the sixth level.

There are $n$ pairwise distinct points on the wall, each can be described as $P_i(x_i, y_i) \;(1\le i\le n)$ in a 2-dimensional rectangular coordinate system.

LZR finds a note board saying that four distinct points $A,B,C,D$ form a flower if there exists a point among the four points strictly inside the triangle formed by the other three points, where the triangle should be non-degenerate.

So the password of this level is naturally the number of tuples $(i,j,k,l)(1 \le i < j < k < l \le n)$ that $P_i, P_j, P_k, P_l$ form a flower.

### 输入描述

The first line contains one positive integer $n$ , denoting the number of points.

Following $n$ lines each contains two integers $x_i, y_i$ , denoting a point.

$4 \le n \le 1000, |x|,|y| \le 10^9$

$n$ points are pairwise distinct.

### 输出描述

Print a non-negative integer in a single line, denoting the number of flowers.

### 示例1

#### 说明

The 5 flowers are

## G - Gemstones

### 题目描述

Gromah and LZR have entered the seventh level. There are a sequence of gemstones on the wall.

After some tries, Gromah discovers that one can take exactly three successive gemstones with the same types away from the gemstone sequence each time, after taking away three gemstones, the left two parts of origin sequence will be merged to one sequence in origin order automatically.

For example, as for “ATCCCTTG”, we can take three ‘C’s away with two parts “AT”, “TTG” left, then the two parts will be merged to “ATTTG”, and we can take three ‘T’s next time.

The password of this level is the maximum possible times to take gemstones from origin sequence.

### 输入描述

Only one line containing a string $s$ , denoting the gemstone sequence, where the same letters are regarded as the same types.

$1 \le |s| \le 10^5$

$s$ only contains uppercase letters.

### 输出描述

Print a non-negative integer in a single line, denoting the maximum times.

### 示例1

#### 说明

One possible way is that $ATCCCTTG \rightarrow ATTTG \rightarrow AG$ .

## H - How Many Schemes

### 题目描述

Gromah and LZR have entered the eighth level. There is an $n$ -vertex tree, acyclic bidirectional connected graph painted on the wall. The vertices are conveniently labeled with $1, 2, \cdots, n$ .

LZR finds that for every edge $e$ in the tree, there is a non-empty set of lowercase letters ses_ese above it. Meanwhile, Gromah finds $m$ strings $t_1, t_2, \cdots, t_m$ and $q$ queries $(u_1, v_1), (u_2, v_2), \cdots, (u_q, v_q)$ beside the tree.

Soon, LZR finds a note board saying that for each query $(u,v)$ , you may choose exactly one letter from ses_ese for all edges $e$ in the chain $u \rightarrow v$ and write down the chosen letters in the order of the directed chain $u\rightarrow v$ to form a string $str$ , and the answer to this query is the number of schemes to choose letters so that the result string $str$ completely contains at least one of the $m$ given strings $t_1, t_2, \cdots, t_m$ .

Moreover, the answers to queries may be very large, so they only need to know the answers modulo $998244353$ .

### 输入描述

The first line contains three positive integers $n,m,q$ , denoting the size of the tree, the number of given strings and the number of queries.

Following $n-1$ lines each contains two positive integers $u,v$ and a string $str_e$ , denoting an edge between $u$ and $v$ with a set $\{c \; | \; c \in str_e\}$ above it.

Following $m$ lines each contains a string $t_i$ .

Following $q$ lines each contains two positive integers $u,v$ , denoting a query $(u,v)$ .

$1\le n\le 2500, 1\le q\le 5000, 1\le m, \sum|t_i| \le 40$

The given graph forms a tree.

$str_e$ only contains pairwise distinct lowercase letters.

$t_i$ only contains lowercase letters.

$u \neq v$ for all queries.

### 输出描述

Output $q$ lines, each contains one non-negative integer denoting the answer to corresponding query modulo $998244353$ .

### 示例1

#### 说明

For the first query, there is no valid scheme.

For the second query, the 6 result strings are $niu, nke, kke, kei, kee, keu$ .

For the third query, the 3 result strings are $ike, eke, uke$ .

## I - Inner World

### 题目描述

Gromah and LZR are transfered to a forest, maybe it is the inner world of the great tomb. Initially, there are $n$ rooted trees numbered from $1$ to $n$ with size $1$ in the forest. For each tree, the only node is the root and labeled with $1$ .

After a while, here comes a farmer, and the farmer gives them $m$ planting tasks, each can be described by a tuple $(u,v,l,r)$ , which means to add a labeled node $v$ for all trees numbered from $l$ to $r$ , and their parent nodes are the nodes labeled with $u$ for each tree.

After finishing the planting tasks one by one, the farmer will give them $q$ querying tasks, each can be described by a tuple $(x,l,r)$ , which means to query the sum of sizes of subtrees whose roots are the nodes labeled with $x$ among the trees numbered from $l$ to $r$ . Specially, if there isn’t a node labeled with $x$ in a tree, the size of subtree $x$ is regarded as $0$ .

If they complete all tasks perfectly, the farmer will help them pass the final level.

### 输入描述

The first line contains two positive integers $n,m$ , denoting the number of trees in the inner world and the number of planting tasks.

Following $m$ lines each contains four positive integers $u,v,l,r$ , denoting a planting task $(u,v,l,r)$ .

The next line contains one positive integer $q$ , denoting the number of querying tasks.

Following $q$ lines each contains four positive integers $x,l,r$ , denoting a querying task $(x,l,r)$ .

$1\le n,m,q \le 300000$ , $1 \le u,x \le m + 1$ , $2 \le v \le m + 1$ , $1 \le l \le r \le n$

For each planting task, It is guaranteed that the label vv_{}v is unique among all vv_{}vs, and the trees numbered from $l$ to $r$ all have a node labeled with $u$ right before handling this task.

### 输出描述

Output $q$ lines, each contains one non-negative integer denoting the answer to corresponding query task.

### 示例1

#### 说明

Four trees are 1-2, 1(-2)-3-4, 1-3-4, 1-3.

In the four trees, sizes of subtrees 1 are 2,4,3,2, so the answer to the first query task is 2+4+3+2=11, while the sizes of subtrees 3 are 0,2,2,1 and the answer to the second query task is 0+2+2+1=5.

## J - Just Jump

### 题目描述

Gromah and LZR have entered the final level. In this level, they need to cross the sea of death to gain the treasures.

The sea of death is of width $L$ , and there are $L-1$ stones inside the sea. Assume that Gromah and LZR are at position $0$ initially, that the treasures are at position $L$ , and that stones are at position $1,2, \cdots, L-1$ respectively. So Gromah and LZR can jump on the stones to cross the sea.

Unfortunately, the stones are not stable. To ensure safety, Gromah and LZR should go forward at least $d$ ositions not less than $x+d$ . Moreover, they can’t be at positions greater than $L$ in any time, which means that the destination of their last jump should be exactly position $L$ , or the treasure keepers will see them and come to eat them.

More unfortunately, the Infernos under the sea will attack them $m$ times in total, each attack can be described as a tuple $(t,p)$ , denoting that the stone at position $p$ will be attacked right after their $t$ -th jump, which means their destination of $t$ -th jump can’t be position $p$

But fortunately, here comes the farmer(mentioned in problem I but not necessary to care in this problem) and he tells Gromah and LZR all the attack plans, so they can work out some jumping plans according to the information given by the farmer to get to the destination without being attacked.

Please help them determine the number of jumping plans satisfying all the restrictions described above. Since the number may be very large, you should report it modulo $998244353$ .

Two jumping plans are considered different if there exists at least one $t$ that their positions after $t$ -th jump are different in two plans.

### 输入描述

The first line contains three positive integers $L,d,m$ , denoting the width of the sea, the lower bound of jumping distance, and the number of attacks.

Following $m$ lines each contains two positive integers $t,p$ denoting an attack $(t,p)$ .

$1 \le d \le L \le 10^7, 1 \le t,p < L, 1 \le m \le 3000$

$m$ attacks are pairwise distinct, where two attacks $(t_1, p_1), (t_2, p_2)$ are considered different if $t_1 \neq t_2$ or $p_1 \neq p_2$ or both.

### 输出描述

Print a non-negative integer in one line, denoting the answer modulo $998244353$ .

### 示例1

#### 说明

There are three plans originally : $0\rightarrow 2 \rightarrow 5, \; 0\rightarrow 3 \rightarrow 5, \; 0\rightarrow 5$ . But after the first jump, the stone at position 2 will be attacked, so plan $0 \rightarrow 2 \rightarrow 5$ should be abandoned and 2 valid plans remain.