ICPC Vietnam National Programming Contest 2020

Start

2020-11-14 16:00 AKST

ICPC Vietnam National Programming Contest 2020

End

2020-11-14 21:00 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -110 days 8:53:14

Time elapsed

5:00:00

Time remaining

0:00:00

Problem E
Easy Arithmetic

Harry is now a third-year student at Hogwarts School of Witchcraft and Wizardry. Contrary to popular belief, arithmetic (known as Arithmancy in the wizard world) is crucial to becoming a powerful wizard.

For today’s Arithmancy homework, Harry is given a super long expression $s$ of length $n$, containing digits, the + and - operators. The $i$-th $(1 \le i \le n)$ character of $s$ is denoted by $s_ i$.

Harry must answer $q$ queries of the following two types:

  1. $? \; \ell \; r$: Compute the value of the expression from the $\ell $-th character to the $r$-th character, inclusive. As the value of this expression can be very large, Harry must calculate it modulo $998\, 244\, 353$.

  2. $! \; i \; c$: Change $s_ i$ to the character $c$.

Please help Harry!

Input

  • The first line contains $n$ characters representing the expression $s$ $(1 \le n \le 10^5)$. It is guaranteed that all characters are either digits or the + and - operators, and no two consecutive characters in $s$ are operators.

  • The second line contains $q$ $(1 \le q \le 10^5)$.

  • In the next $q$ lines, each line contains one query:

    • $? \; \ell \; r$ $(1 \le \ell \le r \le n)$: representing a query of the first type. It is guaranteed that $s_ r$ is a digit.

    • $! \; i \; c$ $(1 \le i \le n)$, $c$ is either a digit or + or -: representing a query of the second type. It is guaranteed that after this query, no two consecutive characters are operators.

Output

For each query of the first type, print the value of the expression, modulo $998\, 244\, 353$.

Sample Input 1 Sample Output 1
123-456+789
10
? 2 5
? 7 9
? 4 6
! 1 +
! 4 0
? 1 7
! 1 -
? 1 3
? 4 7
? 4 5
19
13
998244308
230456
998244330
456
4