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 A, C, G, and T in their DNA with their corresponding strings of length at least 2: $S_A, S_C, S_G$ and $S_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 As, Cs, Gs, and Ts 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 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_{ACGT}$: the $4$ strings $S_A, S_C, S_G, S_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 As, Cs, Gs and Ts in the corresponding queries.

Constraints and clarifications

• $2 \leq S \leq 10^5$, where $S = max(|S_0|, |S_A|, |S_C|, |S_G|, |S_T)$
• It is guaranteed that all letters in the strings are A, C, G, T.
• $1 \leq Q \leq 10^4$
• $0 \leq K_i \leq 10^{18}$ for all $0 \leq i \leq Q-1$
• $0 \leq L_i \leq R_i \leq 10^{18}$ for all $0 \leq i \leq Q-1$
• It is guaranteed that for all queries there exist letters with indices from $L_i$ to $R_i$.

Example

stdin

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

stdout

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

Explanation

The Bad Guys’ DNA for the $0$-th, $1$-st, and $2$-nd day is as follows:

• TAG
• CGCTGTCCT
• CGTCCTCGTCGCCCTCGCCGTCGTCGC

Sample grader

Input format:

• line $1$ to $5$: $S_0, S_A, S_C, S_G, S_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.