No testdata at current.

时间限制： 1.0 秒

空间限制： 512 MB

题目描述

在一个简单文件系统中，有 $n$ 个文件，编号从 $1$ 到 $n$。每个文件存储的数据量，即文件内容的长度，在该文件系统中，叫做“文件大小”，初始文件大小皆为 $0$ 字节。学过计算机系统相关知识的同学都知道，每个文件在硬盘存储时，是以“块”为存储单元。每个文件在硬盘中拥有的存储空间，在该文件系统中，叫做“文件容量”。任何时刻文件容量一定是块大小的非负整数倍。比如，块大小为 $100$ 字节，则任一文件在任何时刻的文件容量一定是 $100$ 字节的非负整数倍。每个文件存储的数据量肯定是不超过其文件容量的，即文件大小不超过文件容量。该文件系统一共有 $m$ 个块，编号从 $1$ 到 $m$，块大小为 $b$，每个块有“已占用”和“未占用”两种状态。

学过计算机系统相关知识的同学都知道，文件内容在逻辑上是连续的，但是在硬盘存储上却不一定是连续的。如图所示，块大小为 $100$ 字节，某个文件大小为 $255$ 字节，文件容量为 $300$ 字节。在逻辑上，文件内容是连续的，但是在硬盘中，是由 $3$ 个编号不连续的块存储着这些数据。该文件系统支持“增改”、“删除”、“查询块”、“查询内容”四种文件操作对文件中的数据进行处理。文件操作可以从某个偏移量 off 开始操作。将整个文件内容看作一个数组，off 就是数组下标，从 $0$ 开始。

• A x off st 表示以第 x 号文件的 off 位置为起点写入数据 st。如果 off 超过文件尾部，则直接从文件尾部开始写入数据。如果 off 及其后面存在旧数据，新数据会覆盖旧数据。在执行写入操作的过程中，如果文件容量不足，该文件系统会为该文件分配“未占用”块以增加文件容量。该文件系统按编号从小到大分配“未占用”块，然后将这些被分配的块标记为“已占用”。如果文件系统“未占用”块不足，则无法增加文件容量，该操作终止，后续部分无效。
• D x off y 表示以第 x 号文件的 off 位置为起点删除 y 字节数据。如果 off 超过文件尾部，则该操作无效。如果以第 x 号文件的 off 位置为起点，已经删除后面所有文件的内容，还未到达 y 字节，该操作终止，后续部分无效。数据删除后，该文件系统会进行空间清理。如图所示，删除后会有一个“空洞”。

• • 空间清理的第一步是，找出数据全部被删除的“已占用”块，将其标记为“未占用”，文件容量也随之减小。如图所示，删除第 $6$ 块。
  • 空间清理的第二步是，连接 off 前后的数据。假设 off 前最后一块数据对应第 $bo_0$ 块，off 开始的数据对应第 $bo_1,bo_2,...,bo_e$ 块。按照 $i=0,1,...,e$ 的顺序处理第 $bo_i$ 块数据。先对第 $bo_i$ 块内部数据 $bo_i^0,bo_i^1,...,bo_i^{b-1}$ 先进行处理。块内位置 $bo_i^l,bo_i^{l+1},...,bo_i^r~(0\le l\le r\le b-1)$ 没有数据。如果 $r<b-1$，从 $bo_i^{r+1}$ 开始将数据前移，否则直接从后面块开始将数据前移，直到第 $bo_i$ 块内存满数据，或者后面块没有数据皆为空。注意，在数据移动过程中，原有位置的数据移动到新位置，原有位置就不再保留数据。第 $bo_i$ 块处理完成后，继续处理后一块数据。处理完第 $e$ 块数据，继续进行空间清理的第三步。如图所示，将第 $9$ 块数据前移到第 $4$ 块。
  • 空间清理的第三步是，继续找出数据全部被删除的“已占用”块，将其标记为“未占用”，文件容量也随之减小。如图所示，删除第 $9$ 块。

• B x 表示查询第 x 号文件拥有的“已占用”块。先返回一个块数，再按文件先后顺序输出“已占用”块的编号。

• C x off y 表示以第 $x$ 号文件的 off 位置为起点查询 y 字节数据。如果 off 超过文件尾部，返回 -2。如果 off 开始的文件内容不足 y 字节，则返回 -1，否则输出对应的 y 字节数据。

现在给出 $k$ 个操作记录，要求实现这个简单文件系统，并输出查询操作的返回结果。保证写入的数据仅有大小写字母，没有其他字符，每个字母占 $1$ 字节的空间。保证 off 一定是非负整数，并且不超过 $10^9$。保证 A 操作的总写入数据量不超过 $10^6$ 字节。

题目保证任意时刻任意文件的大小不超过 $1500$。

输入格式

从标准输入读入数据。

输入的第一行包含四个正整数，$n,m,k,b$，表示 $n$ 个文件，$m$ 个块，$k$ 个操作，以及块大小 $b$。保证 $n\le 10^3，~m\le 10^5,~k\le 10^5,~b\le 10^2$。

接下来 $k$ 行表示 $k$ 个操作，保证 $1\le x \le n,~ 0\le offset\le 10^9,~1\le y\le 10^9$，A 操作中所有 $st$ 长度之和不超过 $10^6$ 字节，且 $st$ 中仅有大小写字母，没有其他字符。

输出格式

输出到标准输出。

每个查询操作输出一行，一共若干行。

2 6 28 3
A 1 2 aAbB
B 1
C 1 0 4
C 1 2 2
C 1 2 3
A 1 2 cCdDeEfFgGhHiIjJkK
B 1
C 1 0 18
C 1 2 8
A 2 0 lL
B 2
C 2 0 1
D 1 4 12
B 1
C 1 0 18
C 1 0 6
A 2 0 lL
B 2
C 2 0 1
D 2 2 20
B 2
C 2 0 1
C 2 0 2
D 2 1 20
B 2
C 2 0 2
C 2 0 1
C 2 100 1

2 1 2
aAbB
bB
-1
6 1 2 3 4 5 6
aAcCdDeEfFgGhHiIjJ
cCdDeEfF
0
-2
2 1 2
-1
aAcCjJ
1 3
l
1 3
l
lL
1 3
-1
l
-2

样例 1 解释

一共有 $2$ 个文件，$6$ 个块，$28$ 个操作，块大小为 $3$。

$1$ 号文件先写入数据 aAbB，拥有 $1,2$ 号块，如下图所示。

$1$ 号文件然后写入 cCdDeEfFgGhHiIjJ，实际数据为 aAcCdDeEfFgGhHiIjJ，拥有 $1,2,3,4,5,6$ 号块，如下图所示。

$2$ 号文件先写入数据 lL，因为空间不足，写入失败。

$1$ 号文件删除数据，实际数据为 aAcCjJ，如下图所示，$3,4,5,6$ 号块被回收。

$2$ 号文件再写入数据 lL，拥有 $3$ 号块，如下图所示。

$2$ 号文件删除数据，实际数据为 lL 。

$2$ 号文件删除数据，实际数据为 l，如下图所示。

2 8 22 3
A 2 0 aaa
B 2
C 2 0 3
A 1 10 aAbBcCdDeEfFgGhHiIjJ
B 1
C 1 0 20
A 1 1 JiIiHhGgFfEeDdCcBbAa
B 1
C 1 0 20
C 1 0 21
D 2 0 3
B 2
C 2 0 1
D 1 9 9
B 1
C 1 0 9
C 1 0 12
C 1 9 3
C 1 8 4
D 1 0 100
B 1
C 1 0 1

1 1
aaa
7 2 3 4 5 6 7 8
aAbBcCdDeEfFgGhHiIjJ
7 2 3 4 5 6 7 8
aJiIiHhGgFfEeDdCcBbA
aJiIiHhGgFfEeDdCcBbAa
0
-2
4 2 3 4 8
aJiIiHhGg
aJiIiHhGgbAa
bAa
gbAa
0
-2

子任务