The 2023 CCPC (Qinhuangdao) Onsite Warmup
A. Water
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Now there are $$$n$$$ people lining up to get some water, the $$$i^{th}$$$ person wants to get $$$c_i$$$ liters of water into his or her bottle.

When the bucket of water on the water dispenser runs out (Each bucket of water provides $$$C$$$ liters of water) , the one who is using the water dispenser (includes the last one) will replace the bucket on the dispenser with a new bucket or water, even if he or she have got enough water. Then he or she leaves right away, so one may leaves with less water than one wants.

Now you want to know how many buckets of water needed (including the first bucket).

Input

The first line contains a single integer $$$T\ (1\le T\le 100)$$$ - the number of testcases.

Each testcase contains two lines.

The first line contains two integers $$$n,C\ (1\le \sum n\le 10^6,1\le C\le 10^3)$$$.

The second line contains $$$n$$$ integers $$$c_i\ (1\le c_i\le10^3)$$$.

Output

For each testcase, print a positive integer representing the number of buckets needed.

Example
Input
4
3 1
6 4 5
4 1
1 6 4 5
2 10
5 2
5 10
8 6 7 10 2
Output
4
5
1
3

B. 810975
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the platypus kingdom, there is a popular game throughout the kingdom–Hearthstone. Hearthstone consists of eight players in each game, and only one of them wins. Due to the difficulty of winning, many platypuses share their best moments of playing the game via live streams. Recently, a Bible "810975" spread.

"810975, why can't newcomers understand?!"

"810975, why are you the only one who doesn't understand?"

...

Recently, Zayin is reciting the Bible 810975 every day. He also continues to explain to his friends the specific meaning of 810975: On August 10, the Platypus King played 9 games and won 7 times, including a 5-game winning streak. But today, there comes a new platypus, Ziyin, who doesn't know the meaning of 810975. So Zayin excitedly explains to him. However, Ziyin has a question, "How many situations are there if I play $$$n$$$ games and win $$$m$$$ games, and the longest winning streak is $$$k$$$?"

If we use 1 to represent victory and 0 to represent defeat, any string consisting of 0 and 1 of length $$$n$$$ can represent a situation of an $$$n$$$-round game. Two situations are different if and only if the two 01 strings are different.

Input

The first line contains three integers $$$n,m,k$$$ ($$$0 \le n,m,k \le 10^5$$$).

Output

The only line contains an integer: the number of situations meeting the constraints. You should output the answer modulo $$$998244353$$$.

Example
Input
9 7 5
Output
9

C. Robot
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Xiaochun, who has just started middle school, has a special fondness for robots. This weekend, she registered for the school's 'Little Robot Club'. After passing several rounds of exams, she finally managed to join the robot club.

Now, Xiaochun has placed her robot on an $$$n\times n$$$ grid, where both rows and columns are numbered from $$$1$$$ to $$$n$$$. She has pre-programmed a sequence of instructions with a length of $$$m$$$ in her remote control. These instructions include U,D,L,R:

  • U: Move from $$$(x,y)$$$ to $$$(x-1,y)$$$.
  • D: Move from $$$(x,y)$$$ to $$$(x+1,y)$$$.
  • L: Move from $$$(x,y)$$$ to $$$(x,y-1)$$$.
  • R: Move from $$$(x,y)$$$ to $$$(x,y+1)$$$.

Specifically, if the robot attempts to move outside the grid, that instruction is invalid.

Xiaochun has conducted a series of experiments, which fall into two categories:

  1. Running experiments: She provides a coordinate $$$(x,y)$$$ to place the robot and specifies a range $$$[l, r]$$$, indicating that the instructions numbered from $$$l$$$ to $$$r$$$ should be executed in sequence.
  2. Modification experiments: She gives a position $$$x$$$ and an instruction $$$c$$$, which means replacing the instruction at the $$$x$$$-th position in the sequence with $$$c$$$.

For each of these experimental runs, Xiaochun wants to know where her robot will ultimately stop, allowing her to verify if her robot's operation is normal.

Input

The first line contains a positive integer $$$T\ (1\le T \le 10)$$$, representing the number of sets of data.

For each set of data:

The first line consists of three integers, $$$n$$$, $$$m$$$, and $$$k$$$, indicating the map's side length, the length of the instruction sequence, and the number of experiments, respectively. $$$(1 \le n, m, k \le 5 \times 10^5)$$$

The second line contains a string of length m, representing the instruction sequence, consisting only of the characters UDLR.

Following are $$$k$$$ lines, each beginning with the integer $$$op$$$, which represents the type of experiment:

  • If $$$op = 1$$$, then the line is followed by four integers $$$x, y, l, r\ (1 \le x,y \le n, 1 \le l \le r \le m)$$$
  • If $$$op = 2$$$, then the line is followed by an integer $$$x\ (1 \le x \le m)$$$ and a character $$$c$$$.

For datasets where $$$max(n,m,k)\ge 100$$$, there will be no more than two such datasets.

Output

For each instruction where $$$op=1$$$, output two numbers $$$x$$$ and $$$y$$$ to represent the final position of the robot.

Example
Input
1
5 5 4
RDRRD
1
5 3 1 5
1
5 1 4 5
2
1 L
1
2 3 1 5
Output
5 5
5 2
4 4