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 (numbered from to ) smaller turntables evenly distributed clockwise starting from the top ( degrees), each of which contains a lamp in the centre and crystals (numbered from to ) evenly distributed around as well. On every small turntable the crystals are all ordered clockwise, with the crystal (starting at ) clockwise from the top (located at degrees relative to the centre of the smaller turntable) having a polish level of .

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

- The large turntable rotates clockwise by 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 degrees rotates clockwise by 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 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 center of the large turntable or each other). Since this value could be very large, output the value modulo .

Please write a program to track of 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:

for all

for all

for all

##### Subtask 1 [27%]

##### Subtask 2 [22%]

##### Subtask 3 [51%]

No additional constraints.

#### Input Specification

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

The next line contains integers. The integer (starting with ), , represents the polish value of the crystal ordered clockwise from the top (located at degrees relative to the centre of the smaller turntable) for all smaller turntables.

The next 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 , indicating that the large turntable should be rotated clockwise by degrees.
- For events of the second type, the next two integers are and , indicating that the turntable currently at degrees should be rotated clockwise by 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 lines, each describing the intensity of the crystal disco turntable.

Output on the first line the initial intensity modulo before the events

Output lines afterwards, with the line describing the intensity of the disco turntable modulo after the first events.

#### Sample Input

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

#### Sample Output

```
189
168
210
252
```

#### Sample Explanation

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

The crystals that are lit up are the larger dots coloured in red around the smaller turntables.

The intensity is measured as

The turntable that has been modified from the first event is indicated with green. The remaining turntables are unchanged.

The intensity is measured as

The intensity is measured as

The turntable that has been modified from the last event is indicated with purple. The remaining turntables are unchanged.

The intensity is measured as

## Comments