Wesley's Anger Contest 6 Problem 8 - Crystal Disco

Points: 30 (partial)

Time limit: 6.0s

Memory limit: 256M

Author:

Problem types

The best way to celebrate a new year is with a disco party!

Wesley's prized possession in the disco party is his special crystal disco turntable. The crystal disco turntable is one large turntable with $N$ ~N~ (numbered from $0$ ~0~ to $N - 1$ ~N - 1~) smaller turntables evenly distributed clockwise starting from the top ( $0$ ~0~ degrees), each of which has a lamp in the centre and $N$ ~N~ crystals (numbered from $0$ ~0~ to $N - 1$ ~N - 1~) evenly distributed around as well. On every small turntable the crystals are all ordered clockwise, with the $i^\text{th}$ ~i^\text{th}~ crystal (starting at $i = 0$ ~i = 0~) clockwise from the top (located at $i \cdot \frac{360}{N}$ ~i \cdot \frac{360}{N}~ degrees relative to the centre of the smaller turntable) having a polish level of $v_i$ ~v_i~.

At the beginning of the party the $N$ ~N~ smaller turntables all have the same orientation. Throughout the course of the party, $2$ ~2~ kinds of events will happen $Q$ ~Q~ times:

The large turntable rotates clockwise by $k_i \cdot \frac{360}{N}$ ~k_i \cdot \frac{360}{N}~ degrees. The smaller turntable orientations do not change relative to the observer's perspective, which can be mapped on the Cartesian plane.
The turntable currently at $q_i \cdot \frac{360}{N}$ ~q_i \cdot \frac{360}{N}~ degrees rotates clockwise by $k_i \cdot \frac{360}{N}$ ~k_i \cdot \frac{360}{N}~ degrees around its centre lamp. The orientation of the other small turntables do not change.

Wesley has asked you to note the initial intensity of the crystal disco as well as the intensity after the $i^\text{th}$ ~i^\text{th}~ event. The intensity is determined as the sum of polish for all crystals that light up. A crystal is only lit up when it is located exactly on the line segment between two lamps on the larger turntable (the smaller turntables are small enough so that the crystals do not intersect at the centre of the large turntable or each other). Since this value could be very large, output the value modulo $998\,244\,353$ ~998\,244\,353~.

Please write a program to track the intensity of the crystal disco over the night!

Constraints

For this problem, you will be required to pass all the samples in order to receive points. In addition, you must pass all previous subtasks to earn points for a specific subtask.

For all subtasks:

$2 \le N \le 200\,000$ ~2 \le N \le 200\,000~
$1 \le Q \le 200\,000$ ~1 \le Q \le 200\,000~
$1 \le v_i \le 1\,000\,000$ ~1 \le v_i \le 1\,000\,000~ for all $0 \le i < N$ ~0 \le i < N~
$0 \le q_i < N$ ~0 \le q_i < N~ for all $1 \le i \le Q$ ~1 \le i \le Q~
$1 \le k_i < N$ ~1 \le k_i < N~ for all $1 \le i \le Q$ ~1 \le i \le Q~

Subtask 1 [27%]

$2 \le N \le 300$ ~2 \le N \le 300~
$1 \le Q \le 300$ ~1 \le Q \le 300~

Subtask 2 [22%]

$2 \le N \le 5\,000$ ~2 \le N \le 5\,000~
$1 \le Q \le 5\,000$ ~1 \le Q \le 5\,000~

Subtask 3 [51%]

No additional constraints.

Input Specification

The first line will contain two integers, $N$ ~N~ and $Q$ ~Q~, representing the number of lamps and crystals, and the number of events.

The next line will contain $N$ ~N~ integers. The $i^\text{th}$ ~i^\text{th}~ integer (starting with $i = 0$ ~i = 0~), $v_i$ ~v_i~, represents the polish value of the $i^\text{th}$ ~i^\text{th}~ crystal ordered clockwise from the top (located at $i \cdot \frac{360}{N}$ ~i \cdot \frac{360}{N}~ degrees relative to the centre of the smaller turntable) for all $N$ ~N~ smaller turntables.

The next $Q$ ~Q~ lines describe the events. Each line begins with a single integer that is either 1 or 2 representing the type of event.

For events of the first type, the next integer is $k_i$ ~k_i~, indicating that the large turntable should be rotated clockwise by $k_i \cdot \frac{360}{N}$ ~k_i \cdot \frac{360}{N}~ degrees.
For events of the second type, the next two integers are $q_i$ ~q_i~ and $k_i$ ~k_i~, indicating that the turntable currently at $q_i \cdot \frac{360}{N}$ ~q_i \cdot \frac{360}{N}~ degrees should be rotated clockwise by $k_i \cdot \frac{360}{N}$ ~k_i \cdot \frac{360}{N}~ degrees around its centre lamp.

Output Specification

This problem is graded with an identical checker. This includes whitespace characters. Ensure that every line of output is terminated with a \n character and that there are no trailing spaces.

Output exactly $Q + 1$ ~Q + 1~ lines, each describing the intensity of the crystal disco turntable.

Output on the first line the initial intensity modulo $998\,244\,353$ ~998\,244\,353~ before the $Q$ ~Q~ events.

Output $Q$ ~Q~ lines afterwards, with the $i^\text{th}$ ~i^\text{th}~ line describing the intensity of the disco turntable modulo $998\,244\,353$ ~998\,244\,353~ after the first $i$ ~i~ events.

Sample Input

6 3
1 2 4 8 16 32
2 1 4
1 5
2 4 2

Sample Output

Sample Explanation

The beginning configuration of the turntable can be seen in the following diagram:

$\text{[math]}$

The crystals that are lit up are the larger dots coloured in red around the $6$ ~6~ smaller turntables.
The intensity is measured as $(16 + 8 + 4) + (32 + 16 + 8) + (1 + 32 + 16) + (32 + 1 + 2) + (1 + 2 + 4) + (2 + 4 + 8) = 189$ .

$\text{[math]}$

The turntable that has been modified from the first event is indicated with green. The remaining turntables are unchanged.
The intensity is measured as $(16 + 8 + 4) + (2 + 1 + 32) + (1 + 32 + 16) + (32 + 1 + 2) + (1 + 2 + 4) + (2 + 4 + 8) = 168$ .

$\text{[math]}$

The intensity is measured as $(1 + 32 + 16) + (32 + 16 + 8) + (1 + 32 + 16) + (32 + 1 + 2) + (1 + 2 + 4) + (2 + 4 + 8) = 210$ .

$\text{[math]}$

The turntable that has been modified from the last event is indicated with purple. The remaining turntables are unchanged.
The intensity is measured as $(1 + 32 + 16) + (32 + 16 + 8) + (1 + 32 + 16) + (32 + 1 + 2) + (16 + 32 + 1) + (2 + 4 + 8) = 252$ .

Comments

There are no comments at the moment.