EIU Programming Practices and Exams

The ABC factory has many manufacturing machines, each machine has an acceptable defect rate and is identified by its unique code. The defect rate of each machine is calculated on the last m product produced. Whenever this rate is exceeded, the management system recognizes the machine's failure and will be repaired immediately by the engineer and the defect rate is re-calculated from the beginning. In the last month, the machines produced n products (including defective products). The company wants to check which machines are regularly repaired to replace, please help the company to find out top k machines which are regularly repaired, if some machines have same rate, output ones with smaller code..

Input

The first line contains 3 integers n and m, k and an acceptable defect rate f (0 <n ≤ 10⁵, 3 <m, k ≤ 1000, 0 ≤ f <1).

In the next N lines, each line is a chronologically-produced product, consisting of the machine code that produced the product and the letter E (defective product) or G (non-defective product).

Output

The list of codes of the most at fault machines, which are sorted by the numnber of repairs (decreasing), then by the code (increasing(. Do not output to non-defective devices.

Example

Input:
11 3 3 0.3
1 E
2 G
1 G
2 E
3 G
1 G
4 G
3 G
3 E
3 E
1 G


Output:
1 3