Limits 1s, 512 MB

On the planet Titan, there are NN residents, numbered from 11 to NN, all employed by Thanos. For each ii from 11 to NN, ithi^{th} person’s salary can be described as SiS_i.

On planet Titan, a network of people can be described as an unweighted directed graph containing NN nodes. Each node represents a person and each edge represents a one-way friendship. There can be duplicate edges. In this network, individuals who share mutual friendships are considered part of the same community. These communities form groups where each member can reach every other member through a series of interconnected friendships.

You need to execute QQ queries on this graph, each falling into one of three categories:

  • ACAC XX YY: Add amount XX to the income of each person within the community to which person YY belongs.

  • ASAS XX YY: Add amount XX to the income of person YY directly.

  • QQ: Determine the maximum individual income across the entire planet and identify the maximum number of people sharing that income within a single community.

Note that the value of the amount XX can be either positive or negative. If an individual's income becomes negative, it indicates they are in debt to Thanos. In case of all negative income in the whole planet, print a single integer 0, otherwise print two integers indicating the maximum individual income across the planet and the maximum number of people who earn that amount within a single community.

Input

The first line of input consists of three integers: NN, MM, and QQ (2N,M,Q2×105)(2 ≤ N, M, Q ≤ 2 × 10^5), representing the number of nodes, the number of edges, and the number of queries to perform, respectively.

Each of the next MM lines contains two integers, UU and VV (1U,VN,UV)(1 ≤ U, V ≤ N, U ≠ V), indicating a directed edge from node UU to VV.

The next line contains NN space-separated integers, denoted as SiS_i (1Si109)(1 ≤ |S_i| ≤ 10^9) for each ii from 11 to NN, representing the salary of the ithi^{th} person.

The following QQ lines each contain one of three types of queries, presented in the following format:

  • ACAC XX YY (1YN,1X109)(1 ≤ Y ≤ N, 1 ≤ |X| ≤ 10^9)

  • ASAS XX YY (1YN,1X109)(1 ≤ Y ≤ N, 1 ≤ |X| ≤ 10^9)

  • QQ

Output

For each of the QQ query types, print two integers SS and PP on a single line separated by a space. SS represents the maximum individual income across the planet, and PP represents the maximum number of people sharing that income within a single community. In case of all negative income in the whole planet, print a single integer 0.

Sample

InputOutput
6 6 16
1 2
2 3
2 4
2 5
5 2
3 6
5 2 3 1 6 10
Q
AC 5 2
Q
AS 4 2
Q
AS 1 6
Q
AS 10 1
Q
AS -100 2
AC -100 1
AC -100 4
AC -100 3
AC -100 6
AC -100 5
Q
10 1
11 1
11 2
11 2
15 1
0

Submit

Login to submit.

Statistics

82% Solution Ratio
ishrak26Earliest, 2w ago
mahirlabibdihanFastest, 0.2s
NadiimLightest, 70 MB
Talha76Shortest, 1917B
Toph uses cookies. By continuing you agree to our Cookie Policy.