Bob has N (1 ≤ N ≤ 2*10^{5}) gears (numbered from 1 to N). Each gear can rotate clockwise or counterclockwise. Bob thinks that assembling gears is much more exciting than just playing with a single one. Bob wants to put some gears into some groups. In each gear group, each gear has a specific rotation respectively, clockwise or counterclockwise, and as we all know, two gears can link together if and only if their rotations are different. At the beginning, each gear itself is a gear group.
Bob has M (1 ≤ N ≤ 4*10^{5}) operations to his gears group:
Since there are so many gears, Bob needs your help.
Input will consist of multiple test cases. In each case, the first line consists of two integers N and M. Following M lines, each line consists of one of the operations which are described above. Please process to the end of input.
3 7 L 1 2 L 2 3 Q 1 3 Q 2 3 D 2 Q 1 3 Q 2 3 5 10 L 1 2 L 2 3 L 4 5 Q 1 2 Q 1 3 Q 1 4 S 1 D 2 Q 2 3 S 1
Link (1, 2), (2, 3), (4, 5), gear 1 and gear 2 have different rotations, and gear 2 and gear 3 have different rotations, so we can know gear 1 and gear 3 have the same rotation, and we didn't link group (1, 2, 3) and group (4, 5), we don't know the situation about gear 1 and gear 4. Gear 1 is in the group (1, 2, 3), which has 3 gears. After putting gear 2 away, it may have a new rotation, and the group becomes (1, 3).