快取記憶體 (Cache) 是一種特別的記憶體，用來縮小讀取中的延遲時間。快取記憶體最基礎的應用就是去保留處理器最常用的的資料，因此現代的處理器使用的主記憶體都擁有一小塊快取記憶體。程式的效能取決於快取的效能，如果資料是在快取記憶體中 (稱為 Hit)，那麼就可以正常的執行；反之，如果資料不在快取記憶體中，程式就會暫停直到資料從主記憶體中讀取進來，計算機架構師總是會去參考快取的 miss 率 (每一百次有多少次資料不在快取中)。
當一次 miss 發生時，新的資料要被放進快取中，而某些舊的資料就要從快取當中移除，這裡有幾個決策法來選擇要移除的資料，一個在計算機系統中最普遍的方法叫做 LRU (最少使用替換演算法，Least Recently Used)，在這個方案裡，最不常用的資料會被移除，讓我們解釋一下這個方案是怎麼運作的。
假設有一個快取有 4 個空間，如果處理器依照 1, 2, 3, 4, 5, 2, 3, 99, 2, 5, 4 的順序拿資料，則狀況如下所述：
| 快取記憶體 | Hit/Miss | 移除資料 |
|---|---|---|
| Miss (1) | ||
| 1 | Miss (2) | |
| 1 2 | Miss (3) | |
| 1 2 3 | Miss (4) | |
| 1 2 3 4 | Miss (5) | 1 |
| 2 3 4 5 | Hit (2) | |
| 2 3 4 5 | Hit (3) | |
| 2 3 4 5 | Miss (99) | 4 |
| 2 3 5 99 | Hit (2) | |
| 2 3 5 99 | Hit (5) | |
| 2 3 5 99 | Miss (4) | 3 |
| 2 4 5 99 |
我們使用了 11 次資料，而有 7 次 miss。在這個問題中，你需要去找出在不同快取記憶體的大小中 miss 的數量，給定以下指令會有以下形式：
ADDR x：處理器會去讀取資料xRANGE b y n：處理器會去讀取形如 $b+y\times{k}$ 的資料，$k$ 的範圍是從 $0$ 到 $n-1$。
你也會收到一個指令 STAT 去印出目前 miss 的數量 (不包括上一個 STAT 之前的指令)，以上範例可以總結如下
RANGE 1 1 5
RANGE 2 1 2
ADDR 99
STAT ---------------------------------- 6
ADDR 2
RANGE 5 -1 2
STAT ---------------------------------- 1
Input
你的程式以一行 $N$ ($1\leq{N}\leq{30}$) 開始，代表有 $N$ 個快取記憶體，接下來有每個快取記憶體的大小 (遞增排序)，快取記憶體的大小至少為 $2$ 且不超過 $2^{20}$。
接下來數行包含 RANGE、ADDR 和 STAT 指令，最後一行有 STAT。所有資料的大小不會超過 $10^7$，對於範例輸入而言，資料總使用次數為 30 次 (5 + 2 + 1 + 1 + 2 + 10 + 5 + 4)，因為處理器是使用 24 位元定址，因此資料範圍不會超過 $2^{24}-1$ 並且是非負的，在 RANGE 中的 $b,y,n$ 和在 ADDR 中的 $x$ 會滿足所有條件。輸入以 END 作為結束，輸入檔有大約 20000 行。
Output
如上所述，對於每個 STAT 指令，印出 miss 數量的一行。
Sample Input
2
4 8
RANGE 1 1 5
RANGE 2 1 2
ADDR 99
STAT
ADDR 2
RANGE 5 -1 2
STAT
RANGE 0 10000 10
RANGE 0 20000 5
RANGE 0 30000 4
STAT
END
Sample Output
6 6
1 0
18 13