Background

LGD is a little dinosaur who likes Monody.

Based on the music of Monody, he built a model called the "String of Monody". For short, SoM (String of Monody).

Problem Description

A "String of Monody" is a string consisting only of $1$, $4$, and $5$. In each operation, LsWn takes a substring with left endpoint $l$ and right endpoint $r$ (note that the first character has index $1$, and the last character has index $n$), and replaces it with a newly given substring. After the replacement, you need to answer $3$ queries about the whole string:

1. The number of $1$'s.
2. The sum of all digits in the whole string.
3. The product of all digits in the whole string.

All outputs should be taken modulo $\color{black}998\color{red}24\color{black}353$.

Input Format

The first line contains a string.
The second line contains an integer $m$, meaning there are $m$ operations.
In the next $m$ lines, each line contains two integers $l, r$, followed by a string of length $r-l+1$, meaning to change the substring $(l, r)$ into this string.

Output Format

Output $m$ lines. Each line contains $3$ integers, representing the $3$ queries after each modification.

114514
3
1 3 111  
3 4 44
4 4 5

4 13 20
3 15 64
3 16 80

Hint

Explanation for Sample 1:

After the first operation, the string becomes 111514. The number of $1$'s is $4$, the sum is $1+1+1+5+1+4=13$, and the product is $1\times 1\times 1\times 1\times 5\times 1\times 4=20$.
After the second operation, the string becomes 114414.
After the third operation, the string becomes 114514.

Let the initial string length be $n$.

For $10\%$ of the testdata, $n\le 10$.
For $40\%$ of the testdata, $n\le 1000$.
For all testdata, $n\le 10^6$, $m\le 10^3$, and $1\le r-l+1\le 10^3$.

Translated by ChatGPT 5