Youngest Boss

A company has no committees and no boards. The only structure is the set of management relations between employees, and one employee may manage other employees while being managed by other employees.

An employee P1 manages an employee P2 in one of two ways. P1 manages P2 directly when P1 is the immediate superior of P2. P1 manages P2 indirectly when P1 directly manages an employee P3 who manages P2 directly or indirectly. No employee manages himself or herself, directly or indirectly.

The figure below shows the chain of command of seven employees with their ages. Part (a) is the starting state, and part (b) is the state after two employees swap their positions in the chain of command.

The company wants to know what role age plays in its organization, so it is building a tool that analyzes the chain of command. The tool processes the instructions in the order they are given. There are two kinds of instruction, a management change and a query.

A management change instruction swaps the positions of employee A and employee B. The positions and the management relations between positions stay as they are, and the two employees exchange positions, each keeping his or her own age. When A and B are the same employee, nothing changes.

A query instruction names an employee E and asks for the age of the youngest employee who manages E directly or indirectly at that moment.

Given the chain of command, the age of every employee and the list of instructions, write a program that answers every query.

The first line contains the number of employees $N$, the number of direct management relations $M$ and the number of instructions $I$, separated by spaces. Employees are identified by the numbers $1$ to $N$.

The second line contains $N$ integers $K_1, K_2, \dots, K_N$, where $K_i$ is the age of employee $i$.

Each of the next $M$ lines contains two integers $X$ and $Y$, meaning that $X$ manages $Y$ directly.

Each of the next $I$ lines contains one instruction. A management change instruction consists of the character T and two integers $A$, $B$, and employees $A$ and $B$ swap positions. A query instruction consists of the character P and one integer $E$, and asks for the age of the youngest employee who manages employee $E$. The last instruction is always a query.

Constraints

• $1 \le N \le 500$
• $0 \le M \le 60000$
• $1 \le I \le 500$
• $1 \le K_i \le 100$ ($1 \le i \le N$)
• $1 \le X, Y \le N$, $X \ne Y$
• $1 \le A, B \le N$
• $1 \le E \le N$
• The management relations given in the input contain no cycle.

For each query instruction, print one line. If at least one employee manages the named employee directly or indirectly, print the age of the youngest such employee. Otherwise print a single asterisk (*).