Greetings, CodeForces users. CodeForces Beta Round #15 will be held today, 29th of May at 19:00 MSK. My name is Roman Iedmeksyi and I am lucky to introduce this problem set.

I would like to thank Dmitry Matov, Julia Satushina and Mike Mirzayanov for well-coordinated work on this match. Also I would like to mention the contribution of Yaroslav Tverdokhlib in problems testing.

Some information about me:

I am a student of Kyiv National Taras Shevchenko University. I started programming at school. As my first achievement I had taken third place in Ukrainian Olympiad in Informatics. Next year I’ve worked harder and was qualified to IOI 2009 selection. Unfortunately I had not enough experience to pass.

In this contest I wish you good luck and high results.

**UPD contest extended by 15 minutes**

**UPD ****Codeforces team apologizes that during today's round the server was regularly unavailable due to different technical reasons. ****We will try to do our best to avoid similar situations on the upcoming contests. Our apologies for some mistakes in the ****statements. Because of these reasons today's competition results will not affect your rating.**

**Looking forward to seeing you at Codeforces Beta Round 16.**

Resuming, you just do the xor of the heights of all towers (nimsum) and check if its equal to zero.

As you have so many towers you can't do this one by one.

If you analise the nimsum sequence from 0 to N, you'll notice that all multiples of 4 have the nimsum value equal to the number. So just iterate from the nearest multiple of 4 till N

One property of the xor is that AxorBxorB = A.

So if you want the NimSum [A..B], you do NimSum[0...A-1]xorNimSum[0...B]