EIU Programming Practices and Exams

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 £ N £ 10⁵).

-      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⁹

Output

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

 Sample