HC - Happy Coins

Happy Coins

A line of coins are given, some belongs to lxh while others belongs to hhb. Now the two guys are about to play a game. In every round of game, each player can select any two consecutive coins and change them into one coin, if the two coins belongs to the same person, the new one will be gained to hhb, or else it will belongs to lxh. The two guys take turns playing this game, lxh always play first. The game runs round by round. You can easily make sense that we will get only one coin at the end of game. Now the question is, suppose the two players perform optimally in the game, which person does the final coin belongs to?


The first line of the input contains one integer T, which indicate the number of test cases.

Following each test, the first line contains an integer N (N ≤ 105), the number of coins. Following N lines, each line contains a name, lxh or hhb, the name of whom this coins belongs to.


For each case, output a line contains the name of whom the final coin belongs to.


Sample Input

Sample Output

hide comments
SangKuan: 2015-07-10 12:21:04

....too easy

apopa: 2015-04-29 13:08:16

The word 'consecutive' is not misleading; it can actually provide a hint. If your solution ignores that requirement and is still accepted, it does not mean that another solution that takes it into account will be rejected. My solution, for example, relies on that requirement and I believe the same holds for many others.

In other words, the comments about the word 'consecutive' being misleading are misleading :)

Ayon Das: 2015-03-26 16:43:21

Think 0's and 1's. XNOR. Cakewalk :)

Govind Lahoti: 2014-09-30 09:20:42

very nice thought behind the prob :)

sobriquet: 2014-07-14 16:30:33

Hint: Take it easy!!!!

ritz: 2014-01-04 08:37:56

(Y) :)

Nishant Gupta: 2013-08-04 13:52:08

nice framing of the question....simple work behind this!!

Nikhil Patil: 2013-06-14 20:51:48

what will be value of new coin generated ??

Last edit: 2013-06-14 20:52:06
Titas Skrebė: 2013-01-14 15:26:30

duhh i put an output line outside the test case loop. dump me :D nice prob. think DP style

Last edit: 2013-01-14 15:27:17

Added by:Kumar Anurag
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)