#216434. [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 , , , and in their DNA with their corresponding strings of length : , , , and . There will be many fights over many days, and so the Good Guys need to make different queries consisting of three numbers -- , , and . For each query, you need to report four numbers, corresponding to the number of s, s, s, and s in the closed interval of the Bad Guys' DNA on the -th day.

Implementation details

You should implement the function :

 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
 )

• : the Bad Guys' DNA on the -th day.
• : the strings .
• : vector of non-negative integers, the -th of which is .
• : vector of non-negative integers, the -th of which is .
• : vector of non-negative integers, the -th of which is .

This function is called exactly once for each test case. It has to return a vector of -element vectors -- the number of s, s, s, and s in the corresponding queries.

Input format:

• line to : .
• line : -- the number of queries.
• line to : , , .

Output format:

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

样例输入 1

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

样例输出 1

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 of the sample

The Bad Guys' DNA for the -th, -st, and -nd day is as follows:

Constraints

• , where
• Is is guaranteed that all letters in the strings are , , , .
• for all
• for all
• It is guaranteed that for all queries there exist letters with indices from to .

Subtasks

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