描述

给定一个长 n 的字符串 a，然后进行 k 次操作，操作一共有两种。(1,t,x,y)表 示将字符串 a 重置为第 t 次操作后的状态，然后将 a 中第 x 个字符修改为 y， (2,t,x)表示将字符串 a 重置为第 t 次操作后的状态，然后删除第 x 个字符，x 之后的字符依次向前补齐。假设 s1,s2,...,sk 为每次操作后得到的字符串，现 在要求将这 k 个字符串进行排序，输出排序结果。 输入

第一行一个整数 n，接下来一行给出字符串 a。 接下来一行一个整数 k，然后是 k 行，表示 k 次操作，保证所有操作均合法。 1 <= n <= 4×106 , 1 <= k <= 600 字符串 a 在任意时刻均只含小写英文字母，并且 a 不会变为空串。 输出

输出一行 n 个整数，第 i 个整数表示字典序第 i 小的字符串的编号，如果字符串 si 和 sj (i<j)的字典序相同，那么先输出 i，后输出 j。 样例输入 样例输出 3 aca 5 1 0 2 e 1 1 2 c 2 2 1 2 3 1 1 0 2 c 4 2 5 1 3 提示

s1 为 aea，s2 为 aca，s3 为 ca，s4 为 a，s5 为 aca