The Fibonacci numbers are defined as follows:

The Fibonacci machine operates on an
-element integer register sequence
which initially contains zeroes only.
The machine provides two operations:
, i.e. adding 1
to the numbers
;
,
i.e. calculating
The first line of the standard input contains two integers
and
(
), separated by a single space and representing the length
of the sequence and the number of operations.
Each of the following
lines contains a description of one operation.
Such a description consists of a character D or S and two integers
and
(
), separated by single spaces.
The character D stands for adding of 1 to the interval
,
and the character S stands for calculating the sum of Fibonacci numbers the
sequence numbers of which are from
.
You may assume that at least one operation of type S appears in the sequence
of operations.
For each operation S write to the standard output exactly one line
with the desired Fibonacci sum. Each result should be calculated modulo
.
For the input data:
5 7 D 1 4 S 1 5 D 3 5 D 2 3 S 1 5 D 2 5 S 2 3
the correct result is:
4 6 5
Explanation of the example: After seven operations the sequence of registers becomes
. The result of the last query is equal to
.
Task author: Tomasz Idziaszek.
W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem szkopul@fri.edu.pl.
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, odwiedź nasze serwery na Discordzie. Są one moderowane przez społeczność, ale członkowie zespołu wsparcia również aktywnie się tam udzielają.