Classified

In the Dynamic Biba integrity model, every user and every document is assigned an integrity level, which measures how reliable its information is. Levels change by two rules:

• When a user writes to a document whose integrity level is higher than the user's, the document's integrity level goes down. In every case the document's new integrity level is the greatest lower bound of the user's level and the document's old level.
• When a user reads a document whose integrity level is lower than the user's, the user's integrity level goes down. In every case the user's new integrity level is the greatest lower bound of the user's old level and the document's level.

Integrity levels are not plain numbers, because one document may hold very trustworthy information about one topic and less trustworthy information about another at the same time. Each level is an arbitrary label, and the levels are ordered by rules of the form A -> B, read as "level A is at most as trustworthy as level B". This order satisfies:

• For every label A, A -> A always holds and need not be listed in the input.
• For two distinct labels A and B, A -> B and B -> A are never both true; it is allowed that neither holds.
• If A -> B and B -> C, then A -> C (even when it is not listed).
• For any two labels A and B there is a label G = glb(A, B), the greatest lower bound, with G -> A and G -> B; moreover every label L such that L -> A and L -> B also satisfies L -> G.

Track the integrity levels of the users and documents as the actions are performed.

Input

• The first line contains five integers l, r, u, d, a: the number of integrity levels, rules, users, documents, and actions. None of them exceeds 10000. Levels are numbered 1 to l, users 1 to u, documents 1 to d.
• Each of the next r lines contains two integers x y (1 <= x, y <= l), meaning x -> y.
• Each of the next u lines contains one integer (1 to l): the initial level of user 1, 2, ..., u.
• Each of the next d lines contains one integer (1 to l): the initial level of document 1, 2, ..., d.
• Each of the next a lines is one action, in one of the two forms below (user is 1 to u, document is 1 to d):
  • user reads document sets the user's level to glb(user's current level, document's level).
  • user writes document sets the document's level to glb(user's level, document's current level).

Output

For each action, in order, print the new integrity level on its own line: the user's new level for a reads action, or the document's new level for a writes action.