P16375 [IATI 2026] Evilution

The Good Guys plan to beat the Bad Guys by shooting them with ionizing radiation. To calibrate their weapons, the Good Guys need to know the composition of some interval of the Bad Guys' DNA. The Bad Guys are not just bad -- they're evil -- and so, they evolve every day by replacing each of the letters $\texttt{A}$, $\texttt{C}$, $\texttt{G}$, and $\texttt{T}$ in their DNA with their corresponding strings of length $\textbf{at least 2}$: $S_\texttt{A}$, $S_\texttt{C}$, $S_\texttt{G}$, and $S_\texttt{T}$. There will be many fights over many days, and so the Good Guys need to make $Q$ different queries consisting of three numbers -- $K_i$, $L_i$, and $R_i$. For each query, you need to report four numbers, corresponding to the number of $\texttt{A}$s, $\texttt{C}$s, $\texttt{G}$s, and $\texttt{T}$s in the closed interval $[L_i; R_i]$ of the Bad Guys' DNA on the $K_i$-th day. ### Implementation details You should implement the function $\texttt{solve}$: ```cpp std::vector solve( std::string S_0, std::vector S_ACGT, std::vector K, std::vector L, std::vector R ) ``` - $S_0$: the Bad Guys' DNA on the $0$-th day. - $S_\texttt{ACGT}$: the $4$ strings $S_\texttt{A}, S_\texttt{C}, S_\texttt{G}, S_\texttt{T}$. - $K$: vector of $Q$ non-negative integers, the $i$-th of which is $K_i$. - $L$: vector of $Q$ non-negative integers, the $i$-th of which is $L_i$. - $R$: vector of $Q$ non-negative integers, the $i$-th of which is $R_i$. This function is called exactly once for each test case. It has to return a vector of $Q$ $4$-element vectors -- the number of $\texttt{A}$s, $\texttt{C}$s, $\texttt{G}$s, and $\texttt{T}$s in the corresponding queries.

Input format: - line $1$ to $5$: $S_0, S_\texttt{A}, S_\texttt{C}, S_\texttt{G}, S_\texttt{T}$. - line $6$: $Q$ -- the number of queries. - line $7$ to $7+(Q-1)$: $K_i$, $L_i$, $R_i$.

Output format: - line $i$ -- the numbers returned by the $i$-th call.

### Explanation of the sample The Bad Guys' DNA for the $0$-th, $1$-st, and $2$-nd day is as follows: - $\tt TAG$ - $\tt CGCTGTCCT$ - $\tt CGTCCTCGTCGCCCTCGCCGTCGTCGC$ ### Constraints - $2 \le S \le 10^5$, where $S = \max(|S_0|, |S_\texttt{A}|, |S_\texttt{C}|, |S_\texttt{G}|, |S_\texttt{T}|)$ - Is is guaranteed that all letters in the strings are $\texttt{A}$, $\texttt{C}$, $\texttt{G}$, $\texttt{T}$. - $1 \le Q \le 10^4$ - $0 \le K_i \le 10^{18}$ for all $0 \le i \le Q-1$ - $0 \le L_i \le R_i \le 10^{18}$ for all $0 \le i \le Q-1$ - It is guaranteed that for all queries there exist letters with indices from $L_i$ to $R_i$. ### Subtasks | **Subtask** | **Points** | **Required subtasks** | **$S$** | **$Q$** | **$K_i$** | **Other constraints** | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | $0$ | $0$ | $-$ | $--$ | $--$ | $--$ | The sample test. | | $1$ | $7$ | $0$ | $\le 5$ | $\le 100$ | $\le 10$ | $--$ | | $2$ | $6$ | $0-1$ | $\le 6$ | $\le 10^4$ | $\le 10$ | $--$ | | $3$ | $13$ | $0-2$ | $\le 10^3$ | $\le 10^4$ | $\le 50$ | $--$ | | $4$ | $10$ | $0-3$ | $\le 10^5$ | $\le 10^4$ | $\le 50$ | $--$ | | $5$ | $15$ | $0-4$ | $\le 10^5$ | $\le 10^4$ | $\le 2 \times 10^3$ | $--$ | | $6$ | $7$ | $-$ | $\le 10^5$ | $\le 10^4$ | $\le 10^{18}$ | $L_i = R_i = 0$. | | $7$ | $17$ | $0-3$ | $\le 10^3$ | $\le 10^4$ | $\le 10^{18}$ | $--$ | | $8$ | $25$ | $0-7$ | $\le 10^5$ | $\le 10^4$ | $\le 10^{18}$ | $--$ | The points for a given subtask are obtained only if all the tests for it and the required subtasks are successfully passed.