Chef and Sets

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Chef passed all the exams. This month was really tiring. So, he decided to relax for a little bit. Well, there is no better way to relax than to play with sets of numbers.
Chef loves to solve problems about sets. That does not mean that he is any good at it. Anyway, he opened his favorite problemset archive, and there he found a task that he thinks is best suited to him.
Problem description
You are given N sets and Q queries. Initially, each set consists only of a single element. The sets are indexed from 1 to N, and the i^{th} set contains the number i. Each query may be one of the following two types.
 UNION a b  merge the a^{th} and the b^{th}. The new set will hold the index N + number of union operations before this one + 1. Also, after this operation, the a^{th} set and the b^{th} set will no longer exist.
 GET a k  find the k^{th} smallest element in the set indexed a
Please help our dear Chef! :)
Input
The first line of the input contains two integers N and Q denoting the number of sets in the very beginning and the number of queries. Each of the next Q lines contains one query per line  either UNION a b" or GET a k.
Output
For each query of second type (i.e. GET) output the number that you've found.
Constraints
 1 ≤ N ≤ 10^{5}
 1 ≤ Q ≤ 2 * 10^{5}.
 All the queries are valid, that is, for any query GET i p, the i^{th} set exists, and has a size of at least p; and for any query UNION a b, the sets indexed as a as well as b exist.
 Subtask 1 (35 points): 1 ≤ N, Q ≤ 500
 Subtask 2 (65 points): 1 ≤ N ≤ 10^{5}, 1 ≤ Q ≤ 2 * 10^{5}
Example
Input: 7 8 UNION 1 2 UNION 8 3 GET 4 1 UNION 4 5 GET 10 2 GET 9 3 GET 9 2 GET 9 1 Output: 4 5 3 2 1
Explanation
 Initially, the sets are: {1}, {2}, {3}, {4}, {5}, {6}, {7}.
 After the first query: {}, {}, {3}, {4}, {5}, {6}, {7}, {1, 2}.
 After the second query the configuration of sets is: {}, {}, {}, {4}, {5}, {6}, {7}, {}, {1, 2, 3}.
 The third query: the set {4} contains only one number so the answer is 4
 The configuration of sets after the fourth query: {}, {}, {}, {}, {}, {6}, {7}, {}, {1, 2, 3}, {4, 5}
 The fifth query: the second smallest element in {4, 5} is 5.
 For queries 6, 7, 8, the set is {1, 2, 3}.
Author:  furko 
Tester:  xcwgf666 
Editorial  http://discuss.codechef.com/problems/CHEFDTRE 
Tags  datastructure, furko, ltime25, medium, orderstatistic, treap 
Date Added:  26062015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 