题目内容

实现字符级 BPE 编码。给定字符串 $text$、合并规则 $merges$ 和词表 $vocab$，返回 token id 列表。

先把 $text$ 拆成单个字符。然后反复检查相邻 token 是否能按 $merges$ 合并。$merges$ 里下标越小优先级越高。每一轮只合并一次：在当前还能合并的相邻对里，选优先级最高的；优先级相同就选最左边。合并后再检查新的相邻对，直到没有任何一对出现在规则里。

最后按 $vocab$ 把剩下的 token 换成 id，按从左到右的顺序返回。保证最终每个 token 都在词表里。规则里的二元组互不相同。token 本身不含空格。

实现 class Solution 的 encode(self, text, merges, vocab)。$text$ 是字符串，$merges$ 是二元组列表，$vocab$ 是 token 到 id 的字典，返回 id 列表。

输入描述

第一行是 $text$。

第二行一个整数 $m$，表示规则条数。接下来 $m$ 行，每行两个 token，表示一条合并规则，顺序就是优先级。

接下来一行一个整数 $v$。再接下来 $v$ 行，每行一个 token 和一个整数 id。

约束

$1 \le |text| \le 2000$

$0 \le m \le 400$

$token$ 只含小写字母，不含空格。

输出描述

一行，按顺序输出 id，用空格隔开。

样例1

输入

abcab
3
a b
b c
ab c
6
a 0
b 1
c 2
ab 3
bc 4
abc 5

输出

5 3

说明

开始是 $\text{a b c a b}$。规则 $(\text{a},\text{b})$ 优先级最高，而且出现了两次，先并最左边，得到 $\text{ab c a b}$，再并右边，得到 $\text{ab c ab}$。接着 $(\text{ab},\text{c})$ 把左边合成 $\text{abc}$。$\text{abc}$ 的 id 是 $5$，$\text{ab}$ 的 id 是 $3$。

样例2

输入

ab
0
2
a 0
b 1

输出

0 1

说明

没有合并规则，两个字符各自对应词表里的 id。