B'There are n cities in Cyberland, numbered from 1 to n, connected by m bidirectional roads. The j-th road connects city aj and bj. For tourists, souvenirs are sold in every city of Cyberland. In particular, city i sell it at a price of wi. Now there are q queries for you to handle. There are two types of queries: More formally, we can define routes as follow: The first line of input contains three integers n, xe2 x80 x89m, xe2 x80 x89q (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89n, xe2 x80 x89m, xe2 x80 x89q xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89105), separated by a single space. Next n lines contain integers wi (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89wi xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89109). Next m lines contain pairs of space-separated integers aj and bj (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89aj, xe2 x80 x89bj xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89n, xe2 x80 x89aj xe2 x80 x89 xe2 x89 xa0 xe2 x80 x89bj). It is guaranteed that there is at most one road connecting the same pair of cities. There is always at least one valid route between any two cities. Next q lines each describe a query. The format is "C a w" or "A a b" (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89a, xe2 x80 x89b xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89n, xe2 x80 x891 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89w xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89109). For each query of type "A", output the corresponding answer. For the second sample, an optimal routes are: From 2 to 3 it is [2, xe2 x80 x893]. From 6 to 4 it is [6, xe2 x80 x895, xe2 x80 x891, xe2 x80 x892, xe2 x80 x894]. From 6 to 7 it is [6, xe2 x80 x895, xe2 x80 x897]. From 3 to 3 it is [3].'...