题目描述

坏人们的 DNA 只由四种字符组成：A、C、G、T。

在第 0 天，坏人的 DNA 为字符串 S_0。之后每天，DNA 都会按照以下规则同时替换：

• 每个 A 替换成字符串 S_A
• 每个 C 替换成字符串 S_C
• 每个 G 替换成字符串 S_G
• 每个 T 替换成字符串 S_T

其中 S_A, S_C, S_G, S_T 的长度都至少为 2。

现在有 Q 个询问。每个询问给出三个整数 K_i, L_i, R_i，你需要回答：

在第 K_i 天的 DNA 串中，闭区间 [L_i, R_i] 内分别有多少个 A、C、G、T？

也就是说，对于每个询问，你需要输出四个数，表示该区间中四种字符各自出现的次数。

实现要求

你需要实现如下函数：

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：第 0 天的 DNA
• S_ACGT：长度为 4 的字符串数组，依次表示 S_A, S_C, S_G, S_T
• K：所有询问中的第 i 个天数 K_i
• L：所有询问中的左端点 L_i
• R：所有询问中的右端点 R_i

函数会被调用恰好一次。
它应返回一个长度为 Q 的二维数组，其中第 i 个元素是一个长度为 4 的数组，依次表示第 i 个询问中 A、C、G、T 的数量。

约束条件

记：

[ S = \max(|S_0|, |S_A|, |S_C|, |S_G|, |S_T|) ]

则有：

• 2 <= S <= 10^5
• 所有字符串中的字符都只会是 A、C、G、T
• 1 <= Q <= 10^4
• 0 <= K_i <= 10^18
• 0 <= L_i <= R_i <= 10^18
• 保证每个询问中，第 K_i 天的 DNA 串至少包含下标从 L_i 到 R_i 的字符

子任务

只有当某个子任务及其要求的前置子任务全部通过时，才能获得该子任务的分数。

样例

输入

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

样例说明

第 0 天、第 1 天、第 2 天的 DNA 分别为：

• TAG
• CGCTGTCCT
• CGTCCTCGTCGCCCTCGCCGTCGTCGC

随后根据各个询问统计指定区间内 A、C、G、T 的个数即可。

本地评测器

输入格式

• 第 1 至 5 行：依次为 S_0, S_A, S_C, S_G, S_T
• 第 6 行：整数 Q
• 第 7 行到第 6 + Q 行：每行三个整数 K_i, L_i, R_i

输出格式

• 第 i 行：四个整数，表示第 i 个询问返回的 A, C, G, T 数量