시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
8 초 128 MB 17 4 4 100.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
W3sicHJvYmxlbV9pZCI6IjI5MjUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyZTBcdWFlMzBcdWQ1NWMgXHViYjNjXHVjY2I0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1YjRcdWIyOTBcdWIwYTAsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWFlMzhcdWM3NDQgXHVhYzc3XHViMzU4IFx1YzkxMVx1YzVkMCBcdWMyZTBcdWFlMzBcdWQ1NWMgXHViYjNjXHVjY2I0XHViOTdjIFx1YmMxY1x1YWNhY1x1ZDU4OFx1YjJlNC4gXHVjNjc4XHVhY2M0XHVjNzU4IFx1YWM4M1x1YzczY1x1Yjg1YyBcdWNkOTRcdWM4MTVcdWI0MThcdWIyOTQgXHVjNzc0IFx1YmIzY1x1Y2NiNFx1Yzc1OCBcdWM2N2NcdWQzYjhcdWM1ZDBcdWIyOTQgXHViZTQ4IFx1YmMxNVx1YzJhNFx1YWMwMCBOXHVhYzFjIFx1Yzc4OFx1YzVjOFx1YjJlNC4gXHVhZTMwXHVhY2M0XHVjNzU4IFx1YzBhY1x1YzZhOVx1YmMyOVx1YmM5NVx1Yzc0NCBcdWM1NGNcdWM1NDRcdWIwYjRcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1ZDU1OFx1YjhlOFx1Yzg4NVx1Yzc3YyBcdWFlMzBcdWFjYzRcdWI5N2MgXHViMzU0XHViNGVjXHVhYzcwXHViODM4XHVhY2UwLCBcdWI5YzhcdWNlNjhcdWIwYjQgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1Yzc3NCBcdWFlMzBcdWFjYzRcdWI5N2MgXHVjNWI0XHViNWJiXHVhYzhjIFx1YzBhY1x1YzZhOVx1ZDU1OFx1YjI5NFx1YzljMFx1Yjk3YyBcdWM1NGNcdWFjOGNcdWI0MThcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcblxyXG5cclxuPHA+XHVhZTMwXHVhY2M0XHViMjk0IFx1YzgxNVx1YzIxOCA0XHVhYzFjIEwsIFIsIEEsIEJcdWI5N2MgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YmMxYlx1YjI5NFx1YjJlNC4gXHVkMDZjXHVhY2UwIFx1YmU2OFx1YWMxYlx1YWM4YyBcdWJlNWJcdWIwOThcdWIyOTQgXHVjMmU0XHVkNTg5XHViYzg0XHVkMmJjXHVjNzQ0IFx1YjIwNFx1Yjk3NFx1YmE3NCBcdWFlMzBcdWFjYzRcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWM2YzBcdWM5YzFcdWM3NzhcdWIyZTQuPFwvcD5cclxuXHJcblxyXG5cclxuPHA+XHViYTNjXHVjODAwLCBMXHViYzg4IFx1YmMxNVx1YzJhNFx1YzVkMCBcdWI0ZTRcdWM1YjQgXHVjNzg4XHViMjk0IFx1YjNjY1x1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgQSBtb2QgQlx1YWMxY1x1Yjg1YyBcdWI5Y2NcdWI0ZTBcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGMgTCsxXHViYzg4IFx1YmMxNVx1YzJhNFx1YzVkMCBcdWI0ZTRcdWM1YjQgXHVjNzg4XHViMjk0IFx1YjNjY1x1Yzc0NCAoMipBKSBtb2QgQlx1YWMxY1x1Yjg1YyBcdWI5Y2NcdWI0ZTBcdWIyZTQuIFx1YjljOFx1Y2MyY1x1YWMwMFx1YzljMFx1Yjg1YywgTCsyXHViYzg4IFx1YmMxNVx1YzJhNFx1YzVkMCBcdWI0ZTRcdWM1YjQgXHVjNzg4XHViMjk0IFx1YjNjY1x1Yzc0NCAoMypBICkgbW9kIEJcdWFjMWNcdWI4NWMgXHViOWNjXHViNGUwXHViMmU0LiBcdWM5ODksIExcdWJjODhcdWFjZmMgUlx1YmM4OCBcdWMwYWNcdWM3NzRcdWM3NTggWFx1YmM4OCBcdWJjMTVcdWMyYTRcdWM1ZDAgXHViNGU0XHVjNWI0IFx1Yzc4OFx1YjI5NCBcdWIzY2NcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjICgoWC1MKzEpKkEpIG1vZCBCXHVhYzFjXHViODVjIFx1YjljY1x1YjRkY1x1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFJcdWJjODggXHViYzE1XHVjMmE0XHVhZTRjXHVjOWMwIFx1YjNjY1x1Yzc0NCBcdWNjNDRcdWM2YjBcdWFjZTBcdWIwOThcdWJhNzQsIFx1YWUzMFx1YWNjNFx1YjI5NCBcdWIyZTRcdWM3NGMgXHViYTg1XHViODM5XHVjNzQ0IFx1YWUzMFx1YjJlNFx1YjliMFx1YjJlNC48XC9wPlxyXG5cclxuXHJcblxyXG48cD5cdWFlMzBcdWFjYzRcdWM1ZDAgXHVjNWVjXHViN2VjXHVhYzAwXHVjOWMwIFx1YmE4NVx1YjgzOVx1Yzc0NCBcdWIwYjRcdWI5YWNcdWIzNTggXHVjOTExXHVjNWQwLCBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNWI0XHViNWE0IFx1YmMxNVx1YzJhNFx1Yzc1OCBcdWFkNmNcdWFjMDRcdWM1ZDAgXHViNGU0XHVjNWI0XHVjNzg4XHViMjk0IFx1YjNjY1x1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVhZDgxXHVhZTA4XHVkNTc0XHVjODRjXHViMmU0LjxcL3A+XHJcblxyXG5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWFlMzBcdWFjYzRcdWM1ZDAgXHVjNzg1XHViODI1XHVkNTVjIFx1YmE4NVx1YjgzOVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM3NzQgXHVhZTMwXHVhY2M0XHViOTdjIFx1YzJkY1x1YmJhY1x1YjgwOFx1Yzc3NFx1ZDMwNSBcdWQ1NThcdWJhNzRcdWMxMWMsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1Yzc1OCBcdWFkODFcdWFlMDhcdWM5OWRcdWIzYzQgXHVkNTc0XHVhY2IwXHVkNTc0XHVjOGZjXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmMxNVx1YzJhNFx1Yzc1OCBcdWMyMTggTlx1YWNmYyBcdWNmZmNcdWI5YWNcdWM3NTggXHVjMjE4IFFcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAxLDAwMCwwMDAsMDAwLCAxICZsZTsgUSAmbGU7IDUwLDAwMCk8XC9wPlxyXG5cclxuXHJcblxyXG48cD5cdWIyZTRcdWM3NGMgUVx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMmRjXHViYmFjXHViODA4XHVjNzc0XHVjMTU4XHVjNWQwIFx1YWQwMFx1ZDU1YyBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG5cclxuXHJcbjxwPlx1YjljY1x1YzU3ZCwgXHVjODE1XHViY2Y0XHVhYzAwIDFcdWI4NWMgXHVjMmRjXHVjNzkxXHVkNTVjXHViMmU0XHViYTc0LCBcdWQ2MTVcdWMyZGRcdWM3NDAgJnF1b3Q7MSBMIFIgQSBCJnF1b3Q7ICgxICZsZTsgTCAmbGU7IFIgJmxlOyBOLCAxICZsZTsgQSwgQiAmbGU7IDEsMDAwLDAwMClcdWFjMDAgXHViNDFjXHViMmU0LiBcdWM3NzQgXHViNzNiXHVjNzQwIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWFlMzBcdWFjYzRcdWM1ZDAgTCwgUiwgQSwgQlx1Yjk3YyBcdWM3ODVcdWI4MjVcdWQ1ODhcdWIyZTRcdWIyOTQgXHViNzNiXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG5cclxuXHJcbjxwPlx1YzgxNVx1YmNmNFx1YWMwMCAyXHViODVjIFx1YzJkY1x1Yzc5MVx1ZDU1Y1x1YjJlNFx1YmE3NCwgXHVkNjE1XHVjMmRkXHVjNzQwICZxdW90OzIgTCBSJnF1b3Q7XHVjNzc0IFx1YjQxY1x1YjJlNC4gKDEgJmxlOyBMICZsZTsgUiAmbGU7IE4pIFx1Yzc3NCBcdWI3M2JcdWM3NDAgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIExcdWFjZmMgUlx1YmM4OCBcdWJjMTVcdWMyYTQgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YjRlNFx1YzViNFx1Yzc4OFx1YjI5NCBcdWIzY2NcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ4MVx1YWUwOFx1ZDU4OFx1YjJlNFx1YjI5NCBcdWI3M2JcdWM3NzRcdWFjZTAsIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NWNcdWI0YTQsIFx1Y2Q5Y1x1YjgyNVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIExcdWFjZmMgUlx1YjNjNCBcdWJjOTRcdWM3MDRcdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDFjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPjJcdWI4NWMgXHVjMmRjXHVjNzkxXHVkNTU4XHViMjk0IFx1YmE4NVx1YjgzOVx1Yzc3NCBcdWI0ZTRcdWM1YjRcdWM2MmMgXHViNTRjIFx1YjljOFx1YjJlNCwgXHVhZGY4IFx1YWQ2Y1x1YWMwNFx1YzVkMCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyOTQgXHViM2NjXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjkyNSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkFMQURJTiIsImRlc2NyaXB0aW9uIjoiPHA+QWxhZGluIHdhcyB3YWxraW5nIGRvd24gdGhlIHBhdGggb25lIGRheSB3aGVuIGhlIGZvdW5kIHRoZSBzdHJhbmdlc3QgdGhpbmcuIE4gZW1wdHkgYm94ZXMgcmlnaHQgbmV4dCB0byBhIHdlaXJkIGFsaWVuIG1hY2hpbmUuIEFmdGVyIGEgYml0IG9mIGZ1bWJsaW5nIGFyb3VuZCBoZSBnb3QgdGhlIG1hY2hpbmUgdG8gZG8gc29tZXRoaW5nLiBUaGUgbWFjaGluZSBub3cgYWNjZXB0cyA0IGludGVnZXJzIEwsIFIsIEEgYW5kIEIuIEFmdGVyIHRoYXQgaGl0dGluZyB0aGUgYmlnIHJlZCBnbG93aW5nIGJ1dHRvbiBsYWJlbGVkICZxdW90O05FRElSQUomcXVvdDsgY2F1c2VzIHRoZSBtYWNoaW5lIHRvIGdvIGNyYXp5IGFuZCBmb2xsb3cgdGhlIG5leHQgcm91dGluZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5TZXQgdGhlIG51bWJlciBvZiBzdG9uZXMgaW4gdGhlIGJveCBsYWJlbGVkIEwgdG8gQSBtb2R1bG8gQi48XC9saT5cclxuXHQ8bGk+SXQgcHJvY2VkZXMgdG8gZmx5IHRvIHRoZSBib3ggbGFiZWxlZCBMKzEsIGFuZCBzZXQgdGhlIG51bWJlciBvZiBzdG9uZXMgdGhlcmUgdG8gKDJcdTIyMTlBKSBtb2QgQi48XC9saT5cclxuXHQ8bGk+SXQgcHJvY2VkZXMgdG8gZmx5IHRvIHRoZSBib3ggbGFiZWxlZCBMKzIsIGFuZCBzZXQgdGhlIG51bWJlciBvZiBzdG9uZXMgdGhlcmUgdG8gKDNcdTIyMTlBKSBtb2QgQi48XC9saT5cclxuXHQ8bGk+R2VuZXJhbHksIGl0IHZpc2l0cyBlYWNoIGJveCBsYWJlbGVkIGJldHdlZW4gTCBhbmQgUiwgYW5kIHNldCB0aGUgbnVtYmVyIG9mIHN0b25lcyB0aGVyZSB0byAoIChYIC0gTCArIDEpXHUyMjE5QSkgbW9kIEIuIHdoZXJlIFggaXMgdGhlIGJveCBsYWJlbC48XC9saT5cclxuXHQ8bGk+QWZ0ZXIgaXQgdmlzaXRzIHRoZSBib3ggbGFiZWxlZCBSLiBJdCBzZXR0bGVzIGRvd24gZm9yIGZ1cnRoZXIgaW5zdHJ1Y3Rpb25zLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkR1cmluZyB0aGUgZ2FtZSBBbGFkaW4gd29uZGVycyB3aGF0IGlzIHRoZSB0b3RhbCBudW1iZXIgb2Ygc3RvbmVzIGluIHNvbWUgcmFuZ2Ugb2YgYm94ZXMuPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IHNpbXVsYXRlcyB0aGUgZGV2aWNlIGFuZCBhbnN3ZXJzIEFsYWRpbnMgcXVlc3Rpb25zLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzIE4gaSBRICgxICZsZTsgTiAmbGU7IDEgMDAwIDAwMCAwMDApICgxICZsZTsgUSAmbGU7IDUwIDAwMCksIG51bWJlciBvZiBib3hlcyBhbmQgbnVtYmVyIG9mIHF1ZXJpZXMuPFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IFEgbGluZXMgY29udGFpbiBpbmZvcm1hdGlvbiBhYm91dCB0aGUgc2ltdWxhdGlvbi48XC9wPlxyXG5cclxuPHA+SWYgdGhlIGxpbmUgc3RhcnRzIHdpdGggMSwgdGhhbiBpdCBmb2xsb3dzIHRoZSBmb3JtYXQgJnF1b3Q7MSBMIFIgQSBCJnF1b3Q7ICgxICZsZTsgTCAmbGU7IFIgJmxlOyBOKSAoMSAmbGU7IEEsIEIgJmxlOyAxMDAwMDAwKSwgbWVhbmluZyB0aGF0IEFsYWRpbiBrZXllZCBpbiBudW1iZXJzIEwsIFIsIEEgYW5kIEIgaW4gdGhlIGRldmljZSBhbmQgYWxsb3dlZCB0aGUgZGV2aWNlIHRvIGRvIGl0cyBqb2IuPFwvcD5cclxuXHJcbjxwPklmIHRoZSBsaW5lIHN0YXJ0cyB3aXRoIDIsIHRoYW4gaXQgZm9sbG93cyB0aGUgZm9ybWF0ICZxdW90OzIgTCBSJnF1b3Q7ICgxICZsZTsgTCAmbGU7IFIgJmxlOyBOKS4gTWVhbmluZyB0aGF0IEFsYWRpbiB3b25kZXJzIGhvdyBtYW55IHN0b25lcyBpbiB0b3RhbCBhcmUgdGhlciBzdG9uZXMgYXJlIGluIGJveGVzIGxhYmVsZWQgTCB0byBSIChpbmNsdXNpdmUpLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHF1ZXJ5IGJlZ2lubmluZyB3aXRoIDIgb3V0cHV0IHRoZSBhbnN3ZXIgdG8gdGhhdCBwYXJ0aWN1bGFyIHF1ZXJ5LiBRdWVyaWVzIHNob3VsZCBiZSBwcm9jZXNzZWQgaW4gdGhlIG9yZGVyIHRoZXkgYXJlIGdpdmVuIGluIHRoZSBpbnB1dC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=