Problem Description

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}$:

 std::vector<std::vector<long long>> solve(
	std::string S_0,
	std::vector<std::string> S_ACGT,
	std::vector<long long> K,
	std::vector<long long> L,
	std::vector<long long> 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

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

Output format:

• line $i$ -- the numbers returned by the $i$-th call.

TAG
TGT
CGT
CCT
CGC
10
1 3 3
2 2 5
0 0 2
0 2 2
0 0 2
1 8 8
0 1 1
1 0 5
0 0 1
1 2 7

0 0 0 1
0 2 0 2
1 0 1 1
0 0 1 0
1 0 1 1
0 0 0 1
1 0 0 0
0 2 2 2
1 0 0 1
0 3 1 2

Hint

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

The points for a given subtask are obtained only if all the tests for it and the required subtasks are successfully passed.