시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB290383159930.671%

문제

동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그 원숭이는 좀 특이한 원숭이였다. 어떤 것도 꿰뚫어볼 수 있는 날카로운 눈을 가진 기이한 원숭이였다. 부드러운 눈을 가진 멍멍이는 언제나 날카로운 눈을 가진 원숭이를 부러워했지만 한편으로는 매우 질투했다.

어느 날 멍멍이는 원숭이의 날카로운 눈이 너무 샘나서 원숭이를 직접 패고 싶었지만 날카로운 눈으로 찌를까봐 무서워서 때리지는 못하고 대신, 원숭이에게 문제 하나를 던져주었다. 그 문제는 다음과 같다.

정수가 여러 개 모여 있는 정수더미가 있다. 그 안에 어떤 특정한 정수 하나만 홀수개 존재하고 나머지 정수는 모두 짝수개 존재한다. 정수더미 속에서 날카로운 눈을 이용해 홀수개 존재하는 정수를 찾아야 하는 문제이다.

근데 멍멍이가 문제를 전달해 주려다가 생각해보니 정수더미 안에 정수가 적게 있으면 문제가 너무 쉬워지게 되는 것이다. 그래서 정수더미안에 정수를 무지막지하게 많이 넣기로 했다. 정수더미가 주어졌을 때, 그 안에 홀수개 존재하는 정수를 찾는 프로그램을 작성하시오.

입력

첫째 줄에 입력의 개수 N이 주어진다. N은 1이상 20,000이하인 수이다. 그 다음 줄부터 N줄에 걸쳐 세 개의 정수 A, C, B가 주어지는데, 이것은 A, A+B, A+2B, ..., A+kB (단, A+kB ≦ C) 의 정수들이 정수더미 안에 있다는 것을 나타낸다. A, B, C는 1보다 크거나 같고 2,147,483,647보다 작거나 같은 정수이다. 정수더미는 N개의 입력이 나타내는 정수들을 모두 포함한다.

출력

첫째 줄에 정수 두 개를 출력하는데, 첫 번째는 홀수개 존재하는 정수를 출력하고, 두 번째는 그 정수가 몇 개 들어있는지 출력한다. 만약 홀수개 존재하는 정수가 없다면 NOTHING을 출력한다.

예제 입력 1

4
1 10 1
4 4 1
1 5 1
6 10 1

예제 출력 1

4 3

힌트

예제로 주어진 정수더미안에는 4가 3개, 4를 제외한 나머지 수들은 각각 2개씩 들어있다. 따라서 답은 “4 3” 이 된다.

W3sicHJvYmxlbV9pZCI6IjE2MzciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIwYTBcdWNlNzRcdWI4NWNcdWM2YjQgXHViMjA4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWIzZDlcdWJiM2NcdWM2ZDBcdWM1ZDBcdWMxMWMgXHViOWM5IFx1ZDBjOFx1Y2Q5Y1x1ZDU1YyBcdWM2ZDBcdWMyMmRcdWM3NzQgXHVkNTVjIFx1YjljOFx1YjlhY1x1YWMwMCBcdWMxMzhcdWMwYzFcdWFkNmNcdWFjYmRcdWM3NDQgXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVhZGY4IFx1YzZkMFx1YzIyZFx1Yzc3NFx1YjI5NCBcdWM4ODAgXHVkMmI5XHVjNzc0XHVkNTVjIFx1YzZkMFx1YzIyZFx1Yzc3NFx1YzYwMFx1YjJlNC4gXHVjNWI0XHViNWE0IFx1YWM4M1x1YjNjNCBcdWFmZjBcdWI2YWJcdWM1YjRcdWJjZmMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWIwYTBcdWNlNzRcdWI4NWNcdWM2YjQgXHViMjA4XHVjNzQ0IFx1YWMwMFx1YzljNCBcdWFlMzBcdWM3NzRcdWQ1NWMgXHVjNmQwXHVjMjJkXHVjNzc0XHVjNjAwXHViMmU0LiBcdWJkODBcdWI0ZGNcdWI3ZWNcdWM2YjQgXHViMjA4XHVjNzQ0IFx1YWMwMFx1YzljNCBcdWJhNGRcdWJhNGRcdWM3NzRcdWIyOTQgXHVjNWI4XHVjODFjXHViMDk4IFx1YjBhMFx1Y2U3NFx1Yjg1Y1x1YzZiNCBcdWIyMDhcdWM3NDQgXHVhYzAwXHVjOWM0IFx1YzZkMFx1YzIyZFx1Yzc3NFx1Yjk3YyBcdWJkODBcdWI3ZWNcdWM2Y2NcdWQ1ODhcdWM5YzBcdWI5Y2MgXHVkNTVjXHVkM2I4XHVjNzNjXHViODVjXHViMjk0IFx1YjllNFx1YzZiMCBcdWM5YzhcdWQyMmNcdWQ1ODhcdWIyZTQuPFwvcD5cclxuPHA+XHVjNWI0XHViMjkwIFx1YjBhMCBcdWJhNGRcdWJhNGRcdWM3NzRcdWIyOTQgXHVjNmQwXHVjMjJkXHVjNzc0XHVjNzU4IFx1YjBhMFx1Y2U3NFx1Yjg1Y1x1YzZiNCBcdWIyMDhcdWM3NzQgXHViMTA4XHViYjM0IFx1YzBkOFx1YjA5OFx1YzExYyBcdWM2ZDBcdWMyMmRcdWM3NzRcdWI5N2MgXHVjOWMxXHVjODExIFx1ZDMyOFx1YWNlMCBcdWMyZjZcdWM1YzhcdWM5YzBcdWI5Y2MgXHViMGEwXHVjZTc0XHViODVjXHVjNmI0IFx1YjIwOFx1YzczY1x1Yjg1YyBcdWNjMGNcdWI5N2NcdWFlNGNcdWJkMTAgXHViYjM0XHVjMTFjXHVjNmNjXHVjMTFjIFx1YjU0Y1x1YjlhY1x1YzljMFx1YjI5NCBcdWJhYmJcdWQ1NThcdWFjZTAgXHViMzAwXHVjMmUwLCBcdWM2ZDBcdWMyMmRcdWM3NzRcdWM1ZDBcdWFjOGMgXHViYjM4XHVjODFjIFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWIzNThcdWM4MzhcdWM4ZmNcdWM1YzhcdWIyZTQuIFx1YWRmOCBcdWJiMzhcdWM4MWNcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG48cD5cdWM4MTVcdWMyMThcdWFjMDAgXHVjNWVjXHViN2VjIFx1YWMxYyBcdWJhYThcdWM1ZWMgXHVjNzg4XHViMjk0IFx1YzgxNVx1YzIxOFx1YjM1NFx1YmJmOFx1YWMwMCBcdWM3ODhcdWIyZTQuIFx1YWRmOCBcdWM1NDhcdWM1ZDAgXHVjNWI0XHViNWE0IFx1ZDJiOVx1YzgxNVx1ZDU1YyBcdWM4MTVcdWMyMTggXHVkNTU4XHViMDk4XHViOWNjIFx1ZDY0MFx1YzIxOFx1YWMxYyBcdWM4NzRcdWM3YWNcdWQ1NThcdWFjZTAgXHViMDk4XHViYTM4XHVjOWMwIFx1YzgxNVx1YzIxOFx1YjI5NCBcdWJhYThcdWI0NTAgXHVjOWRkXHVjMjE4XHVhYzFjIFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNC4gXHVjODE1XHVjMjE4XHViMzU0XHViYmY4IFx1YzE4ZFx1YzVkMFx1YzExYyBcdWIwYTBcdWNlNzRcdWI4NWNcdWM2YjQgXHViMjA4XHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NCBcdWQ2NDBcdWMyMThcdWFjMWMgXHVjODc0XHVjN2FjXHVkNTU4XHViMjk0IFx1YzgxNVx1YzIxOFx1Yjk3YyBcdWNjM2VcdWM1NDRcdWM1N2MgXHVkNTU4XHViMjk0IFx1YmIzOFx1YzgxY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG48cD5cdWFkZmNcdWIzNzAgXHViYTRkXHViYTRkXHVjNzc0XHVhYzAwIFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWM4MDRcdWIyZWNcdWQ1NzQgXHVjOGZjXHViODI0XHViMmU0XHVhYzAwIFx1YzBkZFx1YWMwMVx1ZDU3NFx1YmNmNFx1YjJjOCBcdWM4MTVcdWMyMThcdWIzNTRcdWJiZjggXHVjNTQ4XHVjNWQwIFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4MDFcdWFjOGMgXHVjNzg4XHVjNzNjXHViYTc0IFx1YmIzOFx1YzgxY1x1YWMwMCBcdWIxMDhcdWJiMzQgXHVjMjZjXHVjNmNjXHVjOWMwXHVhYzhjIFx1YjQxOFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YWRmOFx1Yjc5OFx1YzExYyBcdWM4MTVcdWMyMThcdWIzNTRcdWJiZjhcdWM1NDhcdWM1ZDAgXHVjODE1XHVjMjE4XHViOTdjIFx1YmIzNFx1YzljMFx1YjljOVx1YzljMFx1ZDU1OFx1YWM4YyBcdWI5Y2VcdWM3NzQgXHViMTIzXHVhZTMwXHViODVjIFx1ZDU4OFx1YjJlNC4gXHVjODE1XHVjMjE4XHViMzU0XHViYmY4XHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YWRmOCBcdWM1NDhcdWM1ZDAgXHVkNjQwXHVjMjE4XHVhYzFjIFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YjI5NCBcdWM4MTVcdWMyMThcdWI5N2MgXHVjYzNlXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjNzg1XHViODI1XHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gTlx1Yzc0MCAxXHVjNzc0XHVjMGMxIDIwLDAwMFx1Yzc3NFx1ZDU1OFx1Yzc3OCBcdWMyMThcdWM3NzRcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGMgXHVjOTA0XHViZDgwXHVkMTMwIE5cdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1YzEzOCBcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4IEEsIEMsIEJcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0XHViMzcwLCBcdWM3NzRcdWFjODNcdWM3NDAgQSwgQStCLCBBKzJCLCAuLi4sIEEra0IgKFx1YjJlOCwgQStrQiBcdTIyNjYgQykgXHVjNzU4IFx1YzgxNVx1YzIxOFx1YjRlNFx1Yzc3NCBcdWM4MTVcdWMyMThcdWIzNTRcdWJiZjggXHVjNTQ4XHVjNWQwIFx1Yzc4OFx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBBLCBCLCBDXHViMjk0IDFcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCAyLDE0Nyw0ODMsNjQ3XHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LiBcdWM4MTVcdWMyMThcdWIzNTRcdWJiZjhcdWIyOTQgTlx1YWMxY1x1Yzc1OCBcdWM3ODVcdWI4MjVcdWM3NzQgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzgxNVx1YzIxOFx1YjRlNFx1Yzc0NCBcdWJhYThcdWI0NTAgXHVkM2VjXHVkNTY4XHVkNTVjXHViMmU0LjxcL3A+Iiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM4MTVcdWMyMTggXHViNDUwIFx1YWMxY1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWIyOTRcdWIzNzAsIFx1Y2NhYiBcdWJjODhcdWM5ZjhcdWIyOTQgXHVkNjQwXHVjMjE4XHVhYzFjIFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YjI5NCBcdWM4MTVcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVhY2UwLCBcdWI0NTAgXHViYzg4XHVjOWY4XHViMjk0IFx1YWRmOCBcdWM4MTVcdWMyMThcdWFjMDAgXHViYTg3IFx1YWMxYyBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyOTRcdWM5YzAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QgXHVkNjQwXHVjMjE4XHVhYzFjIFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YjI5NCBcdWM4MTVcdWMyMThcdWFjMDAgXHVjNWM2XHViMmU0XHViYTc0IE5PVEhJTkdcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+IiwiaGludCI6IjxwPlx1YzYwOFx1YzgxY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjODE1XHVjMjE4XHViMzU0XHViYmY4XHVjNTQ4XHVjNWQwXHViMjk0IDRcdWFjMDAgM1x1YWMxYywgNFx1Yjk3YyBcdWM4MWNcdWM2NzhcdWQ1NWMgXHViMDk4XHViYTM4XHVjOWMwIFx1YzIxOFx1YjRlNFx1Yzc0MCBcdWFjMDFcdWFjMDEgMlx1YWMxY1x1YzUyOSBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYyBcdWIyZjVcdWM3NDAgJmxkcXVvOzQgMyZyZHF1bzsgXHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTYzNyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlNob3dzdG9wcGVyIiwiZGVzY3JpcHRpb24iOiI8cD5EYXRhLW1pbmluZyBodWdlIGRhdGEgc2V0cyBjYW4gYmUgYSBwYWluZnVsIGFuZCBsb25nIGxhc3RpbmcgcHJvY2VzcyBpZiB3ZSBhcmUgbm90IGF3YXJlIG9mIHRpbnkgcGF0dGVybnMgZXhpc3Rpbmcgd2l0aGluIHRob3NlIGRhdGEgc2V0cy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+T25lIHJlcHV0YWJsZSBjb21wYW55IGhhcyByZWNlbnRseSBkaXNjb3ZlcmVkIGEgdGlueSBidWcgaW4gdGhlaXIgaGFyZHdhcmUgdmlkZW8gcHJvY2Vzc2luZyBzb2x1dGlvbiBhbmQgdGhleSBhcmUgdHJ5aW5nIHRvIGNyZWF0ZSBzb2Z0d2FyZSB3b3JrYXJvdW5kLiBUbyBhY2hpZXZlIG1heGltdW0gcGVyZm9ybWFuY2UgdGhleSB1c2UgdGhlaXIgY2hpcHMgaW4gcGFpcnMgYW5kIGFsbCBkYXRhIG9iamVjdHMgaW4gbWVtb3J5IHNob3VsZCBoYXZlIGV2ZW4gbnVtYmVyIG9mIHJlZmVyZW5jZXMuIFVuZGVyIGNlcnRhaW4gY2lyY3Vtc3RhbmNlcyB0aGlzIHJ1bGUgYmVjYW1lIHZpb2xhdGVkIGFuZCBleGFjdGx5IG9uZSBkYXRhIG9iamVjdCBpcyByZWZlcnJlZCBieSBvZGQgbnVtYmVyIG9mIHJlZmVyZW5jZXMuIFRoZXkgYXJlIHJlYWR5IHRvIGxhdW5jaCBwcm9kdWN0IGFuZCB0aGlzIGlzIHRoZSBvbmx5IHNob3dzdG9wcGVyIHRoZXkgaGF2ZS4gVGhleSBuZWVkIFlPVSB0byBoZWxwIHRoZW0gcmVzb2x2ZSB0aGlzIGNyaXRpY2FsIGlzc3VlIGluIG1vc3QgZWZmaWNpZW50IHdheS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Q2FuIHlvdSBoZWxwIHRoZW0/Jm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5JbnB1dCBmaWxlIGNvbnNpc3RzIGZyb20gbXVsdGlwbGUgZGF0YSBzZXRzIHNlcGFyYXRlZCBieSBvbmUgb3IgbW9yZSBlbXB0eSBsaW5lcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBkYXRhIHNldCByZXByZXNlbnRzIGEgc2VxdWVuY2Ugb2YgMzItYml0IChwb3NpdGl2ZSkgaW50ZWdlcnMgKHJlZmVyZW5jZXMpIHdoaWNoIGFyZSBzdG9yZWQgaW4gY29tcHJlc3NlZCB3YXkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggbGluZSBvZiBpbnB1dCBzZXQgY29uc2lzdHMgZnJvbSB0aHJlZSBzaW5nbGUgc3BhY2Ugc2VwYXJhdGVkIDMyLWJpdCAocG9zaXRpdmUpIGludGVnZXJzIFggWSBaIGFuZCB0aGV5IHJlcHJlc2VudCBmb2xsb3dpbmcgc2VxdWVuY2Ugb2YgcmVmZXJlbmNlczogWCwgWCtaLCBYKzIqWiwgWCszKlosICZoZWxsaXA7LCBYK0sqWiwgJmhlbGxpcDsod2hpbGUgKFgrSypaKSZsdDs9WSkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPllvdXIgdGFzayBpcyB0byBkYXRhLW1pbmUgaW5wdXQgZGF0YSBhbmQgZm9yIGVhY2ggc2V0IGRldGVybWluZSB3ZWF0aGVyIGRhdGEgd2VyZSBjb3JydXB0ZWQsIHdoaWNoIHJlZmVyZW5jZSBpcyBvY2N1cnJpbmcgb2RkIG51bWJlciBvZiB0aW1lcywgYW5kIGNvdW50IHRoYXQgcmVmZXJlbmNlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGlucHV0IGRhdGEgc2V0IHlvdSBzaG91bGQgcHJpbnQgdG8gc3RhbmRhcmQgb3V0cHV0IG5ldyBsaW5lIG9mIHRleHQgd2l0aCBlaXRoZXIgJmxkcXVvO05PVEhJTkcmcmRxdW87ICh1cHBlciBjYXNlKSBvciB0d28gaW50ZWdlcnMgc2VwYXJhdGVkIGJ5IHNpbmdsZSBzcGFjZSAoZmlyc3Qgb25lIGlzIHJlZmVyZW5jZSB0aGF0IG9jY3VycyBvZGQgbnVtYmVyIG9mIHRpbWVzIGFuZCBzZWNvbmQgb25lIGlzIGNvdW50IG9mIHRoYXQgcmVmZXJlbmNlKS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

ICPC > Regionals > Europe > Southeastern European Regional Contest > SEERC 2007 E번