Your friend came up with an idea of starting a social network-SOCNET. Since, he is not as good a programmer as you are he needs your help to build certain features.

You need to build an ADD friend feature. if 'x' sends a friend request to 'y', he may accept it or deny it.

SOCNET has a special feature called 'community'. When two people 'x' and 'y' becomes friends, the communities of two are merged together. (If 'x' has no friends, it's community consist of only himself, size-1)

Since, your friend is low on funds, the data center he uses has a restriction-the MAXIMUM size of any community cannot exceed 'm'.

You need to work on following three types of queries-

• A x y - x sends a friend request to y
• E x y - check whether x and y are present in same community (print 'Yes' or 'No')
• S x - prints the size of the community 'x' belongs to.

NOTE- A friend requested is accepted only if the merger of the two communities results in a community not greater than 'm'.

Input

The first line of input consists of two positive integers - n and m(n is the number of registered users and m is the maximum size of any community).

Next line consist of a positive integer q (number of queries).

q lines follows (Each line consist of a query as described in the problem statement).

The queries follows 1-indexing.

Constraints

1<=n, m<=100000, 1<=q<=200000

Output

For each query of Type - 'E', output in a single line-'Yes' or 'No'. For each query of Type - 'S', output the size of the community to which 'x' belongs. For further clarification, read the example given.

Example

Input:
5 3
8
S 2
A 2 3
E 2 3
S 2
A 4 5
A 3 5
E 3 5
S 3

Output:
1
Yes
2
No
2

Explanation

Initially no one has any friend. So community of '2' consist of only '2' i.e. size-1. Then '2' and '3' becomes friends .This forms a community of 2 people. '4' and '5' also becomes friends. This forms another community of 2 people. '5' is unable to accept friend request of '3' (because it would result in a community of 4 people(>3).

---

hide comments

< Previous 1 2 Next >
	lakshya1st: 2020-09-07 17:18:37 Basic DSU implementation!!
	mritunjya: 2020-05-13 13:15:42 50th question ac in one go
	yeerk16: 2019-10-01 23:27:35 I quite like this problem -- but the time limit is loose and accepts union-find without any optimization (union by rank/size, path compression). Does anyone know a similar problem (e.g. pure union-find) where smarter union-find is required? Thanks!
	scolar_fuad: 2019-08-15 07:13:22 Simple dsu ..... Nice for beginner
	aryan29: 2019-06-05 22:41:23 My first DSU good one for beginners
	jkks1234: 2018-01-17 13:45:21 https://www.hackerearth.com/practice/notes/disjoint-set-union-union-find/
	akashranjan28: 2017-06-27 20:43:39 easiest one... it gave me 0.4 points take care of "Yes"/"No" ,costed me 1 WA
	Siddharth Singh: 2016-06-17 12:39:31 Silly Mistake Costed Me 3 WA's BC :|
	ankit_amazon: 2016-03-21 21:21:20 Good one!
	Arjav: 2016-01-24 01:38:23 Direct DSU :)