By Leonardo Alt Brazil
Conan is an important member of the Desrugenstein Athletic Club, which has a football professional team. Conan is the responsible for the the home matches field's grass. In 2048 years of history, DAC's field has always been in perfect conditions for the matches, thanks to Conan. He already earned many prizes for that. The most important was the “Golden Grass”, prize won 1024 times by Conan.
Tomorrow CAD will play (and host) the Universal Football Championship finals. The match will be at home, so Conan went to check the grass state and repair if necessary. When he arrived there, he despaired when he saw many schweisen in the field, spoiling the grass!!
Now Conan needs your help to calculate how much money he will spend buying deswevileutssen to kill all the schweisen. Each deswevileutssen kills one schweisen. Conan can send you messages of two types: saying he found some schweisen, or asking how much he will spend to kill certain schweisen.
Input contains several test cases. First line of a test case contains 3 integers X (≤ 1000), Y (≤ 1000) and P (≤ 10) representing, respectively, field's size (X, Y) and the price for each deswevileutssen. Next line contains an integer Q (≤ 10000). Next Q lines represent messages from Conan to you, and they are in one of the following two forms:
- A N X Y - “I found N (≤ 10) schweisen at (X,Y) - (0 ≤ X < Width), (0 ≤ Y < Height)”
- P X Y Z W – “How much money do I need to kill every schweisen inside the rectangular area from (X, Y) to (Z, W)?”
Consider that in the beginning no schweisen was seen.
Input ends when X, Y and P = 0.
For each message of type “P”, print the answer for the question. Leave a blank line after each test case.
|Input Sample||Output Sample|
2 2 10