SOCNETC - Social Network Community

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).


Added by:Prateek Agarwal
Date:2015-12-20
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY

hide comments
2016-01-18 20:20:16 Prateek Agarwal
@levim-Either way is right.
2016-01-14 23:56:13
Do you print the results of all querys at the end of input or do you print after each query?
2015-12-27 19:49:00
AC in one go :)
2015-12-20 17:36:32 abdou_93
Tutorial
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.