시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
8 초 128 MB 67 11 9 60.000%

문제

어느 날, 상근이는 길을 걷던 중에 신기한 물체를 발견했다. 외계의 것으로 추정되는 이 물체의 왼편에는 빈 박스가 N개 있었다. 기계의 사용방법을 알아내기 위해서 하루종일 기계를 더듬거렸고, 마침내 상근이는 이 기계를 어떻게 사용하는지를 알게되었다.

기계는 정수 4개 L, R, A, B를 입력으로 받는다. 크고 빨갛게 빛나는 실행버튼을 누르면 기계는 다음과 같은 움직인다.

먼저, L번 박스에 들어 있는 돌의 개수를 A mod B개로 만든다. 그 다음 L+1번 박스에 들어 있는 돌을 (2*A) mod B개로 만든다. 마찬가지로, L+2번 박스에 들어 있는 돌을 (3*A ) mod B개로 만든다. 즉, L번과 R번 사이의 X번 박스에 들어 있는 돌의 개수를 ((X-L+1)*A) mod B개로 만드는 것이다. R번 박스까지 돌을 채우고나면, 기계는 다음 명령을 기다린다.

기계에 여러 가지 명령을 내리던 중에, 상근이는 어떤 박스의 구간에 들어있는 돌의 개수가 궁금해졌다.

상근이가 기계에 입력한 명령이 주어졌을 때, 이 기계를 시뮬레이팅 하면서, 상근이의 궁금증도 해결해주는 프로그램을 작성하시오.

입력

첫째 줄에 박스의 수 N과 쿼리의 수 Q가 주어진다. (1 ≤ N ≤ 1,000,000,000, 1 ≤ Q ≤ 50,000)

다음 Q개 줄에는 시뮬레이션에 관한 정보가 주어진다.

만약, 정보가 1로 시작한다면, 형식은 "1 L R A B" (1 ≤ L ≤ R ≤ N, 1 ≤ A, B ≤ 1,000,000)가 된다. 이 뜻은 상근이가 기계에 L, R, A, B를 입력했다는 뜻이다.

정보가 2로 시작한다면, 형식은 "2 L R"이 된다. (1 ≤ L ≤ R ≤ N) 이 뜻은 상근이가 L과 R번 박스 사이에 들어있는 돌의 개수를 궁금했다는 뜻이고, 개수를 구한뒤, 출력해야 한다. L과 R도 범위에 포함된다.

출력

2로 시작하는 명령이 들어올 때 마다, 그 구간에 들어있는 돌의 개수를 출력한다.

예제 입력 1

6 3
2 1 6
1 1 5 1 2
2 1 6

예제 출력 1

0
3
W3sicHJvYmxlbV9pZCI6IjI5MjUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyZTBcdWFlMzBcdWQ1NWMgXHViYjNjXHVjY2I0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1YjRcdWIyOTAgXHViMGEwLCBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVhZTM4XHVjNzQ0IFx1YWM3N1x1YjM1OCBcdWM5MTFcdWM1ZDAgXHVjMmUwXHVhZTMwXHVkNTVjIFx1YmIzY1x1Y2NiNFx1Yjk3YyBcdWJjMWNcdWFjYWNcdWQ1ODhcdWIyZTQuIFx1YzY3OFx1YWNjNFx1Yzc1OCBcdWFjODNcdWM3M2NcdWI4NWMgXHVjZDk0XHVjODE1XHViNDE4XHViMjk0IFx1Yzc3NCBcdWJiM2NcdWNjYjRcdWM3NTggXHVjNjdjXHVkM2I4XHVjNWQwXHViMjk0IFx1YmU0OCBcdWJjMTVcdWMyYTRcdWFjMDAgTlx1YWMxYyBcdWM3ODhcdWM1YzhcdWIyZTQuIFx1YWUzMFx1YWNjNFx1Yzc1OCBcdWMwYWNcdWM2YTlcdWJjMjlcdWJjOTVcdWM3NDQgXHVjNTRjXHVjNTQ0XHViMGI0XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWQ1NThcdWI4ZThcdWM4ODVcdWM3N2MgXHVhZTMwXHVhY2M0XHViOTdjIFx1YjM1NFx1YjRlY1x1YWM3MFx1YjgzOFx1YWNlMCwgXHViOWM4XHVjZTY4XHViMGI0IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM3NzQgXHVhZTMwXHVhY2M0XHViOTdjIFx1YzViNFx1YjViYlx1YWM4YyBcdWMwYWNcdWM2YTlcdWQ1NThcdWIyOTRcdWM5YzBcdWI5N2MgXHVjNTRjXHVhYzhjXHViNDE4XHVjNWM4XHViMmU0LjxcL3A+XHJcblxyXG5cclxuXHJcbjxwPlx1YWUzMFx1YWNjNFx1YjI5NCBcdWM4MTVcdWMyMTggNFx1YWMxYyBMLCBSLCBBLCBCXHViOTdjIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWJjMWJcdWIyOTRcdWIyZTQuIFx1ZDA2Y1x1YWNlMCBcdWJlNjhcdWFjMWJcdWFjOGMgXHViZTViXHViMDk4XHViMjk0IFx1YzJlNFx1ZDU4OVx1YmM4NFx1ZDJiY1x1Yzc0NCBcdWIyMDRcdWI5NzRcdWJhNzQgXHVhZTMwXHVhY2M0XHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVjNmMwXHVjOWMxXHVjNzc4XHViMmU0LjxcL3A+XHJcblxyXG5cclxuXHJcbjxwPlx1YmEzY1x1YzgwMCwgTFx1YmM4OCBcdWJjMTVcdWMyYTRcdWM1ZDAgXHViNGU0XHVjNWI0IFx1Yzc4OFx1YjI5NCBcdWIzY2NcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIEEgbW9kIEJcdWFjMWNcdWI4NWMgXHViOWNjXHViNGUwXHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjIEwrMVx1YmM4OCBcdWJjMTVcdWMyYTRcdWM1ZDAgXHViNGU0XHVjNWI0IFx1Yzc4OFx1YjI5NCBcdWIzY2NcdWM3NDQgKDIqQSkgbW9kIEJcdWFjMWNcdWI4NWMgXHViOWNjXHViNGUwXHViMmU0LiBcdWI5YzhcdWNjMmNcdWFjMDBcdWM5YzBcdWI4NWMsIEwrMlx1YmM4OCBcdWJjMTVcdWMyYTRcdWM1ZDAgXHViNGU0XHVjNWI0IFx1Yzc4OFx1YjI5NCBcdWIzY2NcdWM3NDQgKDMqQSApIG1vZCBCXHVhYzFjXHViODVjIFx1YjljY1x1YjRlMFx1YjJlNC4gXHVjOTg5LCBMXHViYzg4XHVhY2ZjIFJcdWJjODggXHVjMGFjXHVjNzc0XHVjNzU4IFhcdWJjODggXHViYzE1XHVjMmE0XHVjNWQwIFx1YjRlNFx1YzViNCBcdWM3ODhcdWIyOTQgXHViM2NjXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyAoKFgtTCsxKSpBKSBtb2QgQlx1YWMxY1x1Yjg1YyBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBSXHViYzg4IFx1YmMxNVx1YzJhNFx1YWU0Y1x1YzljMCBcdWIzY2NcdWM3NDQgXHVjYzQ0XHVjNmIwXHVhY2UwXHViMDk4XHViYTc0LCBcdWFlMzBcdWFjYzRcdWIyOTQgXHViMmU0XHVjNzRjIFx1YmE4NVx1YjgzOVx1Yzc0NCBcdWFlMzBcdWIyZTRcdWI5YjBcdWIyZTQuPFwvcD5cclxuXHJcblxyXG5cclxuPHA+XHVhZTMwXHVhY2M0XHVjNWQwIFx1YzVlY1x1YjdlYyBcdWFjMDBcdWM5YzAgXHViYTg1XHViODM5XHVjNzQ0IFx1YjBiNFx1YjlhY1x1YjM1OCBcdWM5MTFcdWM1ZDAsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM1YjRcdWI1YTQgXHViYzE1XHVjMmE0XHVjNzU4IFx1YWQ2Y1x1YWMwNFx1YzVkMCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyOTQgXHViM2NjXHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWFkODFcdWFlMDhcdWQ1NzRcdWM4NGNcdWIyZTQuPFwvcD5cclxuXHJcblxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YWUzMFx1YWNjNFx1YzVkMCBcdWM3ODVcdWI4MjVcdWQ1NWMgXHViYTg1XHViODM5XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1Yzc3NCBcdWFlMzBcdWFjYzRcdWI5N2MgXHVjMmRjXHViYmFjXHViODA4XHVjNzc0XHVkMzA1IFx1ZDU1OFx1YmE3NFx1YzExYywgXHVjMGMxXHVhZGZjXHVjNzc0XHVjNzU4IFx1YWQ4MVx1YWUwOFx1Yzk5ZFx1YjNjNCBcdWQ1NzRcdWFjYjBcdWQ1NzRcdWM4ZmNcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViYzE1XHVjMmE0XHVjNzU4IFx1YzIxOCBOXHVhY2ZjIFx1Y2ZmY1x1YjlhY1x1Yzc1OCBcdWMyMTggUVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDEsMDAwLDAwMCwwMDAsIDEgJmxlOyBRICZsZTsgNTAsMDAwKTxcL3A+XHJcblxyXG5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBRXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMyZGNcdWJiYWNcdWI4MDhcdWM3NzRcdWMxNThcdWM1ZDAgXHVhZDAwXHVkNTVjIFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcblxyXG5cclxuPHA+XHViOWNjXHVjNTdkLCBcdWM4MTVcdWJjZjRcdWFjMDAgMVx1Yjg1YyBcdWMyZGNcdWM3OTFcdWQ1NWNcdWIyZTRcdWJhNzQsIFx1ZDYxNVx1YzJkZFx1Yzc0MCAmcXVvdDsxIEwgUiBBIEImcXVvdDsgKDEgJmxlOyBMICZsZTsgUiAmbGU7IE4sIDEgJmxlOyBBLCBCICZsZTsgMSwwMDAsMDAwKVx1YWMwMCBcdWI0MWNcdWIyZTQuIFx1Yzc3NCBcdWI3M2JcdWM3NDAgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YWUzMFx1YWNjNFx1YzVkMCBMLCBSLCBBLCBCXHViOTdjIFx1Yzc4NVx1YjgyNVx1ZDU4OFx1YjJlNFx1YjI5NCBcdWI3M2JcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcblxyXG5cclxuPHA+XHVjODE1XHViY2Y0XHVhYzAwIDJcdWI4NWMgXHVjMmRjXHVjNzkxXHVkNTVjXHViMmU0XHViYTc0LCBcdWQ2MTVcdWMyZGRcdWM3NDAgJnF1b3Q7MiBMIFImcXVvdDtcdWM3NzQgXHViNDFjXHViMmU0LiAoMSAmbGU7IEwgJmxlOyBSICZsZTsgTikgXHVjNzc0IFx1YjczYlx1Yzc0MCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgTFx1YWNmYyBSXHViYzg4IFx1YmMxNVx1YzJhNCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNGU0XHVjNWI0XHVjNzg4XHViMjk0IFx1YjNjY1x1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhZDgxXHVhZTA4XHVkNTg4XHViMmU0XHViMjk0IFx1YjczYlx1Yzc3NFx1YWNlMCwgXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1Y1x1YjRhNCwgXHVjZDljXHViODI1XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gTFx1YWNmYyBSXHViM2M0IFx1YmM5NFx1YzcwNFx1YzVkMCBcdWQzZWNcdWQ1NjhcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Mlx1Yjg1YyBcdWMyZGNcdWM3OTFcdWQ1NThcdWIyOTQgXHViYTg1XHViODM5XHVjNzc0IFx1YjRlNFx1YzViNFx1YzYyYyBcdWI1NGMgXHViOWM4XHViMmU0LCBcdWFkZjggXHVhZDZjXHVhYzA0XHVjNWQwIFx1YjRlNFx1YzViNFx1Yzc4OFx1YjI5NCBcdWIzY2NcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyOTI1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQUxBRElOIiwiZGVzY3JpcHRpb24iOiI8cD5BbGFkaW4gd2FzIHdhbGtpbmcgZG93biB0aGUgcGF0aCBvbmUgZGF5IHdoZW4gaGUgZm91bmQgdGhlIHN0cmFuZ2VzdCB0aGluZy4gTiBlbXB0eSBib3hlcyByaWdodCBuZXh0IHRvIGEgd2VpcmQgYWxpZW4gbWFjaGluZS4gQWZ0ZXIgYSBiaXQgb2YgZnVtYmxpbmcgYXJvdW5kIGhlIGdvdCB0aGUgbWFjaGluZSB0byBkbyBzb21ldGhpbmcuIFRoZSBtYWNoaW5lIG5vdyBhY2NlcHRzIDQgaW50ZWdlcnMgTCwgUiwgQSBhbmQgQi4gQWZ0ZXIgdGhhdCBoaXR0aW5nIHRoZSBiaWcgcmVkIGdsb3dpbmcgYnV0dG9uIGxhYmVsZWQgJnF1b3Q7TkVESVJBSiZxdW90OyBjYXVzZXMgdGhlIG1hY2hpbmUgdG8gZ28gY3JhenkgYW5kIGZvbGxvdyB0aGUgbmV4dCByb3V0aW5lOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlNldCB0aGUgbnVtYmVyIG9mIHN0b25lcyBpbiB0aGUgYm94IGxhYmVsZWQgTCB0byBBIG1vZHVsbyBCLjxcL2xpPlxyXG5cdDxsaT5JdCBwcm9jZWRlcyB0byBmbHkgdG8gdGhlIGJveCBsYWJlbGVkIEwrMSwgYW5kIHNldCB0aGUgbnVtYmVyIG9mIHN0b25lcyB0aGVyZSB0byAoMlx1MjIxOUEpIG1vZCBCLjxcL2xpPlxyXG5cdDxsaT5JdCBwcm9jZWRlcyB0byBmbHkgdG8gdGhlIGJveCBsYWJlbGVkIEwrMiwgYW5kIHNldCB0aGUgbnVtYmVyIG9mIHN0b25lcyB0aGVyZSB0byAoM1x1MjIxOUEpIG1vZCBCLjxcL2xpPlxyXG5cdDxsaT5HZW5lcmFseSwgaXQgdmlzaXRzIGVhY2ggYm94IGxhYmVsZWQgYmV0d2VlbiBMIGFuZCBSLCBhbmQgc2V0IHRoZSBudW1iZXIgb2Ygc3RvbmVzIHRoZXJlIHRvICggKFggLSBMICsgMSlcdTIyMTlBKSBtb2QgQi4gd2hlcmUgWCBpcyB0aGUgYm94IGxhYmVsLjxcL2xpPlxyXG5cdDxsaT5BZnRlciBpdCB2aXNpdHMgdGhlIGJveCBsYWJlbGVkIFIuIEl0IHNldHRsZXMgZG93biBmb3IgZnVydGhlciBpbnN0cnVjdGlvbnMuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+RHVyaW5nIHRoZSBnYW1lIEFsYWRpbiB3b25kZXJzIHdoYXQgaXMgdGhlIHRvdGFsIG51bWJlciBvZiBzdG9uZXMgaW4gc29tZSByYW5nZSBvZiBib3hlcy48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgc2ltdWxhdGVzIHRoZSBkZXZpY2UgYW5kIGFuc3dlcnMgQWxhZGlucyBxdWVzdGlvbnMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0d28gaW50ZWdlcnMgTiBpIFEgKDEgJmxlOyBOICZsZTsgMSAwMDAgMDAwIDAwMCkgKDEgJmxlOyBRICZsZTsgNTAgMDAwKSwgbnVtYmVyIG9mIGJveGVzIGFuZCBudW1iZXIgb2YgcXVlcmllcy48XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgUSBsaW5lcyBjb250YWluIGluZm9ybWF0aW9uIGFib3V0IHRoZSBzaW11bGF0aW9uLjxcL3A+XHJcblxyXG48cD5JZiB0aGUgbGluZSBzdGFydHMgd2l0aCAxLCB0aGFuIGl0IGZvbGxvd3MgdGhlIGZvcm1hdCAmcXVvdDsxIEwgUiBBIEImcXVvdDsgKDEgJmxlOyBMICZsZTsgUiAmbGU7IE4pICgxICZsZTsgQSwgQiAmbGU7IDEwMDAwMDApLCBtZWFuaW5nIHRoYXQgQWxhZGluIGtleWVkIGluIG51bWJlcnMgTCwgUiwgQSBhbmQgQiBpbiB0aGUgZGV2aWNlIGFuZCBhbGxvd2VkIHRoZSBkZXZpY2UgdG8gZG8gaXRzIGpvYi48XC9wPlxyXG5cclxuPHA+SWYgdGhlIGxpbmUgc3RhcnRzIHdpdGggMiwgdGhhbiBpdCBmb2xsb3dzIHRoZSBmb3JtYXQgJnF1b3Q7MiBMIFImcXVvdDsgKDEgJmxlOyBMICZsZTsgUiAmbGU7IE4pLiBNZWFuaW5nIHRoYXQgQWxhZGluIHdvbmRlcnMgaG93IG1hbnkgc3RvbmVzIGluIHRvdGFsIGFyZSB0aGVyIHN0b25lcyBhcmUgaW4gYm94ZXMgbGFiZWxlZCBMIHRvIFIgKGluY2x1c2l2ZSkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggcXVlcnkgYmVnaW5uaW5nIHdpdGggMiBvdXRwdXQgdGhlIGFuc3dlciB0byB0aGF0IHBhcnRpY3VsYXIgcXVlcnkuIFF1ZXJpZXMgc2hvdWxkIGJlIHByb2Nlc3NlZCBpbiB0aGUgb3JkZXIgdGhleSBhcmUgZ2l2ZW4gaW4gdGhlIGlucHV0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==