Background

在算法竞赛中寻找操作系统是否搞错了什么？

Description

你需要模拟操作系统中一种叫做LRU页面置换算法的工作过程。假设有一个固定大小的驻留集，用来存放正在使用的页面（也就是数据块）。当访问一个页面时，如果页面已经在驻留集中，就直接使用；如果不在，就称为缺页，需要把该页面调入驻留集。

驻留集大小固定为N，如果缺页时驻留集已经满了，就需要把其中最久没有被访问过的页面换出（也就是从驻留集中移除），然后把新的页面调入。换出的页面如果曾经被写过（即写回位为1），就需要记录下来，等一定数量（阈值M）后统一写回到硬盘。

你会接收到若干页面访问请求，每个请求包含页面号 (P) 和访问类型 (S)，访问类型是一个长度为2的二进制字符串，第一位表示是否读（1 表示读，0 表示不读），第二位表示是否写（1 表示写，0 表示不写）。例如：

• “10” 表示读操作，
• “01” 表示写操作，
• “11” 表示读写操作。

初始时驻留集为空。

模拟过程：

初始时驻留集为空。

处理每次访问请求时，执行以下操作：

1. 若页面 $P$ 已在驻留集中，将其标记为“最近使用”。

2. 若页面 $P$ 不在驻留集中，则发生缺页：

   • 若驻留集未满，直接将页面 $P$ 加入。
   • 若驻留集已满，使用 LRU 算法选择最久未使用的页面换出：
     • 若换出的页面的写回位为 1（曾被写过），则将其加入“待写回队列”。
   • 然后将页面 $P$ 加入驻留集。

3. 若访问类型包含写操作（即访问类型的第 2 位为 1），将该页面的写回位设置为 1。

4. 每当“待写回队列”中的页面数达到阈值 $M$ 时：

   • 将这些页面写回（输出），并清空该队列。

5. 所有访问处理结束后，如果“待写回队列”仍不为空，也应执行一次写回。

Format

Input

• 第一行包含三个整数 $N$、$M$、$C$（驻留集大小、写回阈值、访问次数）：

  • $1 \le N, M, C \le 1000$

• 接下来 $C$ 行，每行包含一个整数 $P$（页面编号）和一个长度为 2 的二进制字符串 $S$（访问类型）：

  • $0 \le P < 2^{20}$
  • $S \in \{\texttt{"00"}, \texttt{"01"}, \texttt{"10"}, \texttt{"11"}\}$

Output

对于每次访问请求，输出一行，包含两个数字，用空格隔开：

• 若该次访问导致缺页，输出 1，否则输出 0
• 若该次缺页导致页面换出，输出 1，否则输出 0

每次发生写回操作时，输出一行：

  write_back k x1 x2 ... xk

其中 $k$ 是写回页面数，$x_1, x_2, ..., x_k$ 为被写回的页面号，按升序排列。

Samples

3 2 7
1 10
2 11
3 11
4 11
2 10
5 11
1 11

1 0
1 0
1 0
1 1
0 0
1 1
1 1
write_back 2 3 4

• 第 4 次访问换出页面 1，但其写回位为 0，因此不加入写回队列。
• 第 6 次访问换出页面 3，它写回位为 1，加入队列。此时队列有 2 页，达到阈值，执行写回。
• 第 7 次访问换出页面 4，它写回位为 1，加入队列。此时队列有 2 页，达到阈值，执行写回。
• 访问结束后，队列中为空，不需再次写回。