Description

在现代计算机中，程序使用的是虚拟地址，CPU访问内存时需要将虚拟地址转换为物理地址，整个过程涉及快表（TLB）、页表和缓存（Cache）三种结构。快表是CPU内部用于加速虚拟页号到物理页号转换的小容量缓存，页表记录虚拟页号与物理页号的映射关系，缓存用于存储最近访问的物理内存数据块以提高访问速度。现模拟CPU对虚拟地址的访问过程，统计每次访问中快表命中与否、页表是否命中（或缺页）、缓存是否命中。

访存过程详细说明

1. 虚拟地址拆分

   • 从32位虚拟地址中提取：
     • 高20位作为虚拟页号（VPN，Virtual Page Number）。
     • 低12位作为页内偏移（Offset），表示页内具体地址。

2. 查询快表（TLB）

   • 查找快表中是否存在该虚拟页号对应的物理页号（PPN，Physical Page Number）。
   • 如果找到（TLB命中）：
     • 直接获得对应的物理页号，进入步骤4。
   • 如果未找到（TLB未命中）：
     • 进入步骤3查询页表。

3. 查询页表

   • 在页表中查找该虚拟页号对应的物理页号。
   • 如果页表中存在映射（页表命中）：
     • 将该映射加入快表。
     • 若快表已满，则淘汰最近最少使用（LRU）的条目。
     • 进入步骤4。
   • 如果页表中无对应映射（缺页，页表未命中）：
     • 访问失败，结束本次访问。
     • 输出相应状态。

4. 计算物理地址

   • 由物理页号左移12位加上页内偏移，得到完整物理地址。

5. 查询缓存（Cache）

   • 计算缓存行号（例如使用物理地址的某些位对缓存行数取模）。
   • 检查该缓存行存储的数据标签是否与物理地址标签匹配。
   • 如果匹配（缓存命中）：
     • 访问缓存成功。
   • 如果不匹配（缓存未命中）：
     • 需要从物理内存加载该数据块。
     • 更新缓存行中的标签和有效位。

6. 输出访问状态

   • 输出本次访问的：
     • 快表是否命中（TLB_HIT / TLB_MISS）。
     • 页表是否命中或缺页（PAGE_HIT / PAGE_MISS）。
     • 缓存是否命中（CACHE_HIT / CACHE_MISS）。
   • 注意：如果发生缺页（PAGE_MISS），缓存状态统一输出CACHE_MISS。

Format

Input

第一行包含四个整数：N M C Q

• N — 物理页数（1 ≤ N ≤ 2^16）
• M — 快表容量（1 ≤ M ≤ 2^14）
• C — 缓存行数（1 ≤ C ≤ 2^14）
• Q — 访问次数（1 ≤ Q ≤ 10^5）

接下来 N 行，第 i 行包含一个整数 P_i（-1 ≤ P_i < 2^20），表示物理页 i 映射的虚拟页号，若为 -1 表示无映射。

接下来 Q 行，每行一个无符号 32 位整数，以十进制的形式给出，表示访问的虚拟地址。

Output

对于每次访问，输出一行，包含三个用空格分隔的状态：

TLB_HIT/MISS PAGE_HIT/MISS CACHE_HIT/MISS 具体含义如下：

• TLB（快表）状态

  • TLB_HIT 表示快表中找到了该虚拟页号对应的物理页号。
  • TLB_MISS 表示快表中未找到该虚拟页号映射。

• 页表状态

  • PAGE_HIT 表示页表中存在对应的物理页号。
  • PAGE_MISS 表示页表中不存在对应的物理页号，发生缺页异常（访问失败，此时缓存状态统一为 CACHE_MISS）。

• 缓存状态

  • CACHE_HIT 表示缓存中存在对应物理地址的数据块。
  • CACHE_MISS 表示缓存中没有对应数据块，需要从物理内存加载并更新缓存。
  • 当页表状态为 PAGE_MISS 时，缓存状态固定输出 CACHE_MISS。

Samples

4 2 4 5
0
1
-1
3
4096
8192
12288
4096
61440

TLB_MISS PAGE_HIT CACHE_MISS
TLB_MISS PAGE_HIT CACHE_MISS
TLB_MISS PAGE_MISS CACHE_MISS
TLB_HIT PAGE_HIT CACHE_HIT
TLB_MISS PAGE_HIT CACHE_MISS