Given the list of check-in and check-out time of employees. Calculate the wage of the employees. By default, each employee earns ~X~ KVND per hour. However, there are ~M~ employees who have different hourly wage rates because of their performance.

Input

• The first line contains four integers ~N~ - the number of employees, ~X, M, K~ – the number of check-in/check-out records ~(1 \leq N \leq 10^5)~.

• The second line contains ~N~ integers which are the id of employees.

• Each line in the next ~M~ lines contains two integers ~a, b~ representing that employee who has id equals to ~a~, earn ~b~ VN per hour.

• Each line in the next ~K~ lines contains two integers representing a check-in/check-out record. The first integer is the id of the employee. The second integer is the time of check-in/check-out

• All integers don't not exceed ~10^9~.

Output

• For each employee in ascending order of id, output the id and the wage.

Sample Input

3 40 1 6
1 2 3
1 60
1 4
2 4
1 5
1 6
2 8
1 11

Sample Output

1 360
2 160
3 0