在奇幻大陆上，有 $N$ 位年轻魔法师，每人都拥有一些属于自己的魔法宝石。魔法师们可以自由结盟组成公会，共同管理和增值宝藏。

题目描述

大陆上有 $N$ 位魔法师，编号为 $1$ 到 $N$。 第 $i$ 位魔法师初始拥有 $W_i$ 颗魔法宝石，并且每个人最初都属于一个独立的公会（公会里只有他自己）。

随后，会发生 $M$ 次事件，事件类型如下：

1. 结盟 (JOIN u v)： 魔法师 $u$ 和魔法师 $v$ 所在的公会决定合并成一个新的公会。 • 如果 $u$ 和 $v$ 已经在同一公会中，则无需操作。 • 合并后，两个公会的所有魔法师都归属于新公会。
2. 宝藏查询 (QUERY u )： 公会会长想知道魔法师 $u$ 所在公会的宝藏情况。你需要回答两个问题： • 公会中所有魔法师宝石的总和 • 公会中拥有最多宝石的魔法师拥有的宝石数

输入格式 • 第一行包含两个整数 $N$ 和 $M$，分别表示魔法师数量和事件数量。 • 第二行包含 $N$ 个整数 $W_1, W_2, \dots, W_N$，表示每位魔法师初始拥有的宝石数。 • 接下来 $M$ 行，每行描述一个事件： • JOIN u v：表示魔法师 $u$ 和 $v$ 的公会合并 • QUERY u ：表示查询魔法师 $u$ 所在公会的宝藏信息

输出格式

对于每个 QUERY 事件，输出一行两个整数，由空格分隔。 第一个整数表示该公会的宝石总和，第二个整数表示该公会中最多宝石的魔法师拥有的宝石数。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示混混的数量和事件的数量。 第二行包含 $N$ 个整数 $W_1, W_2, \dots, W_N$，表示每个混混初始的存款金额。 接下来 $M$ 行，每行描述一个事件：

• JOIN u v
• QUERY u

输出格式

对于每一个 QUERY 事件，输出一行包含两个整数，由空格分隔。 第一个整数表示该公会的存款总和，第二个整数表示该公会中的最大存款金额。

输入输出样例 #1

输入 #1

5 6
10 20 30 40 50
QUERY 1
JOIN 1 2
JOIN 2 3
QUERY 1
JOIN 4 5
QUERY 5

输出 #1

10 10
60 30
90 50

说明/提示

数据范围

• $1 \leq N, M \leq 10^5$
• $0 \leq W_i \leq 10^9$