시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
8 초 128 MB 30 6 6 85.714%

문제

어느날, 상근이는 길을 걷던 중에 신기한 물체를 발견했다. 외계의 것으로 추정되는 이 물체의 왼편에는 빈 박스가 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+XHViYTNjXHVjODAwLCBMXHViYzg4IFx1YmMxNVx1YzJhNFx1YzVkMCBcdWI0ZTRcdWM1YjQgXHVjNzg4XHViMjk0IFx1YjNjY1x1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgQSBtb2QgQlx1YWMxY1x1Yjg1YyBcdWI5Y2NcdWI0ZTBcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGMgTCsxXHViYzg4IFx1YmMxNVx1YzJhNFx1YzVkMCBcdWI0ZTRcdWM1YjQgXHVjNzg4XHViMjk0IFx1YjNjY1x1Yzc0NCAoMipBKSBtb2QgQlx1YWMxY1x1Yjg1YyBcdWI5Y2NcdWI0ZTBcdWIyZTQuIFx1YjljOFx1Y2MyY1x1YWMwMFx1YzljMFx1Yjg1YywgTCsyXHViYzg4IFx1YmMxNVx1YzJhNFx1YzVkMCBcdWI0ZTRcdWM1YjQgXHVjNzg4XHViMjk0IFx1YjNjY1x1Yzc0NCAoMypBICkgbW9kIEJcdWFjMWNcdWI4NWMgXHViOWNjXHViNGUwXHViMmU0LiBcdWM5ODksIExcdWJjODhcdWFjZmMgUlx1YmM4OCBcdWMwYWNcdWM3NzRcdWM3NTggWFx1YmM4OCBcdWJjMTVcdWMyYTRcdWM1ZDAgXHViNGU0XHVjNWI0IFx1Yzc4OFx1YjI5NCBcdWIzY2NcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjICgoWC1MKzEpKkEpIG1vZCBCXHVhYzFjXHViODVjIFx1YjljY1x1YjRkY1x1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFJcdWJjODggXHViYzE1XHVjMmE0XHVhZTRjXHVjOWMwIFx1YjNjY1x1Yzc0NCBcdWNjNDRcdWM2YjBcdWFjZTBcdWIwOThcdWJhNzQsIFx1YWUzMFx1YWNjNFx1YjI5NCBcdWIyZTRcdWM3NGMgXHViYTg1XHViODM5XHVjNzQ0IFx1YWUzMFx1YjJlNFx1YjliMFx1YjJlNC48XC9wPlxyXG5cclxuXHJcblxyXG48cD5cdWFlMzBcdWFjYzRcdWM1ZDAgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMCBcdWJhODVcdWI4MzlcdWM3NDQgXHViMGI0XHViOWFjXHViMzU4IFx1YzkxMVx1YzVkMCwgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YzViNFx1YjVhNCBcdWJjMTVcdWMyYTRcdWM3NTggXHVhZDZjXHVhYzA0XHVjNWQwIFx1YjRlNFx1YzViNFx1Yzc4OFx1YjI5NCBcdWIzY2NcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YWQ4MVx1YWUwOFx1ZDU3NFx1Yzg0Y1x1YjJlNC48XC9wPlxyXG5cclxuXHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVhZTMwXHVhY2M0XHVjNWQwIFx1Yzc4NVx1YjgyNVx1ZDU1YyBcdWJhODVcdWI4MzlcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNzc0IFx1YWUzMFx1YWNjNFx1Yjk3YyBcdWMyZGNcdWJiYWNcdWI4MDhcdWM3NzRcdWQzMDUgXHVkNTU4XHViYTc0XHVjMTFjLCBcdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHVhZDgxXHVhZTA4XHVjOTlkXHViM2M0IFx1ZDU3NFx1YWNiMFx1ZDU3NFx1YzhmY1x1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJjMTVcdWMyYTRcdWM3NTggXHVjMjE4IE5cdWFjZmMgXHVjZmZjXHViOWFjXHVjNzU4IFx1YzIxOCBRXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMSwwMDAsMDAwLDAwMCwgMSAmbGU7IFEgJmxlOyA1MCwwMDApPFwvcD5cclxuXHJcblxyXG5cclxuPHA+XHViMmU0XHVjNzRjIFFcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzJkY1x1YmJhY1x1YjgwOFx1Yzc3NFx1YzE1OFx1YzVkMCBcdWFkMDBcdWQ1NWMgXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuXHJcblxyXG48cD5cdWI5Y2NcdWM1N2QsIFx1YzgxNVx1YmNmNFx1YWMwMCAxXHViODVjIFx1YzJkY1x1Yzc5MVx1ZDU1Y1x1YjJlNFx1YmE3NCwgXHVkNjE1XHVjMmRkXHVjNzQwICZxdW90OzEgTCBSIEEgQiZxdW90OyAoMSAmbGU7IEwgJmxlOyBSICZsZTsgTiwgMSAmbGU7IEEsIEIgJmxlOyAxLDAwMCwwMDApXHVhYzAwIFx1YjQxY1x1YjJlNC4gXHVjNzc0IFx1YjczYlx1Yzc0MCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVhZTMwXHVhY2M0XHVjNWQwIEwsIFIsIEEsIEJcdWI5N2MgXHVjNzg1XHViODI1XHVkNTg4XHViMmU0XHViMjk0IFx1YjczYlx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuXHJcblxyXG48cD5cdWM4MTVcdWJjZjRcdWFjMDAgMlx1Yjg1YyBcdWMyZGNcdWM3OTFcdWQ1NWNcdWIyZTRcdWJhNzQsIFx1ZDYxNVx1YzJkZFx1Yzc0MCAmcXVvdDsyIEwgUiZxdW90O1x1Yzc3NCBcdWI0MWNcdWIyZTQuICgxICZsZTsgTCAmbGU7IFIgJmxlOyBOKSBcdWM3NzQgXHViNzNiXHVjNzQwIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBMXHVhY2ZjIFJcdWJjODggXHViYzE1XHVjMmE0IFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyOTQgXHViM2NjXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkODFcdWFlMDhcdWQ1ODhcdWIyZTRcdWIyOTQgXHViNzNiXHVjNzc0XHVhY2UwLCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTVjXHViNGE0LCBcdWNkOWNcdWI4MjVcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBMXHVhY2ZjIFJcdWIzYzQgXHViYzk0XHVjNzA0XHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD4yXHViODVjIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YjI5NCBcdWJhODVcdWI4MzlcdWM3NzQgXHViNGU0XHVjNWI0XHVjNjJjIFx1YjU0YyBcdWI5YzhcdWIyZTQsIFx1YWRmOCBcdWFkNmNcdWFjMDRcdWM1ZDAgXHViNGU0XHVjNWI0XHVjNzg4XHViMjk0IFx1YjNjY1x1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI5MjUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJBTEFESU4iLCJkZXNjcmlwdGlvbiI6IjxwPkFsYWRpbiB3YXMgd2Fsa2luZyBkb3duIHRoZSBwYXRoIG9uZSBkYXkgd2hlbiBoZSBmb3VuZCB0aGUgc3RyYW5nZXN0IHRoaW5nLiBOIGVtcHR5IGJveGVzIHJpZ2h0IG5leHQgdG8gYSB3ZWlyZCBhbGllbiBtYWNoaW5lLiBBZnRlciBhIGJpdCBvZiBmdW1ibGluZyBhcm91bmQgaGUgZ290IHRoZSBtYWNoaW5lIHRvIGRvIHNvbWV0aGluZy4gVGhlIG1hY2hpbmUgbm93IGFjY2VwdHMgNCBpbnRlZ2VycyBMLCBSLCBBIGFuZCBCLiBBZnRlciB0aGF0IGhpdHRpbmcgdGhlIGJpZyByZWQgZ2xvd2luZyBidXR0b24gbGFiZWxlZCAmcXVvdDtORURJUkFKJnF1b3Q7IGNhdXNlcyB0aGUgbWFjaGluZSB0byBnbyBjcmF6eSBhbmQgZm9sbG93IHRoZSBuZXh0IHJvdXRpbmU6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+U2V0IHRoZSBudW1iZXIgb2Ygc3RvbmVzIGluIHRoZSBib3ggbGFiZWxlZCBMIHRvIEEgbW9kdWxvIEIuPFwvbGk+XHJcblx0PGxpPkl0IHByb2NlZGVzIHRvIGZseSB0byB0aGUgYm94IGxhYmVsZWQgTCsxLCBhbmQgc2V0IHRoZSBudW1iZXIgb2Ygc3RvbmVzIHRoZXJlIHRvICgyXHUyMjE5QSkgbW9kIEIuPFwvbGk+XHJcblx0PGxpPkl0IHByb2NlZGVzIHRvIGZseSB0byB0aGUgYm94IGxhYmVsZWQgTCsyLCBhbmQgc2V0IHRoZSBudW1iZXIgb2Ygc3RvbmVzIHRoZXJlIHRvICgzXHUyMjE5QSkgbW9kIEIuPFwvbGk+XHJcblx0PGxpPkdlbmVyYWx5LCBpdCB2aXNpdHMgZWFjaCBib3ggbGFiZWxlZCBiZXR3ZWVuIEwgYW5kIFIsIGFuZCBzZXQgdGhlIG51bWJlciBvZiBzdG9uZXMgdGhlcmUgdG8gKCAoWCAtIEwgKyAxKVx1MjIxOUEpIG1vZCBCLiB3aGVyZSBYIGlzIHRoZSBib3ggbGFiZWwuPFwvbGk+XHJcblx0PGxpPkFmdGVyIGl0IHZpc2l0cyB0aGUgYm94IGxhYmVsZWQgUi4gSXQgc2V0dGxlcyBkb3duIGZvciBmdXJ0aGVyIGluc3RydWN0aW9ucy48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5EdXJpbmcgdGhlIGdhbWUgQWxhZGluIHdvbmRlcnMgd2hhdCBpcyB0aGUgdG90YWwgbnVtYmVyIG9mIHN0b25lcyBpbiBzb21lIHJhbmdlIG9mIGJveGVzLjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCBzaW11bGF0ZXMgdGhlIGRldmljZSBhbmQgYW5zd2VycyBBbGFkaW5zIHF1ZXN0aW9ucy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBOIGkgUSAoMSAmbGU7IE4gJmxlOyAxIDAwMCAwMDAgMDAwKSAoMSAmbGU7IFEgJmxlOyA1MCAwMDApLCBudW1iZXIgb2YgYm94ZXMgYW5kIG51bWJlciBvZiBxdWVyaWVzLjxcL3A+XHJcblxyXG48cD5UaGUgbmV4dCBRIGxpbmVzIGNvbnRhaW4gaW5mb3JtYXRpb24gYWJvdXQgdGhlIHNpbXVsYXRpb24uPFwvcD5cclxuXHJcbjxwPklmIHRoZSBsaW5lIHN0YXJ0cyB3aXRoIDEsIHRoYW4gaXQgZm9sbG93cyB0aGUgZm9ybWF0ICZxdW90OzEgTCBSIEEgQiZxdW90OyAoMSAmbGU7IEwgJmxlOyBSICZsZTsgTikgKDEgJmxlOyBBLCBCICZsZTsgMTAwMDAwMCksIG1lYW5pbmcgdGhhdCBBbGFkaW4ga2V5ZWQgaW4gbnVtYmVycyBMLCBSLCBBIGFuZCBCIGluIHRoZSBkZXZpY2UgYW5kIGFsbG93ZWQgdGhlIGRldmljZSB0byBkbyBpdHMgam9iLjxcL3A+XHJcblxyXG48cD5JZiB0aGUgbGluZSBzdGFydHMgd2l0aCAyLCB0aGFuIGl0IGZvbGxvd3MgdGhlIGZvcm1hdCAmcXVvdDsyIEwgUiZxdW90OyAoMSAmbGU7IEwgJmxlOyBSICZsZTsgTikuIE1lYW5pbmcgdGhhdCBBbGFkaW4gd29uZGVycyBob3cgbWFueSBzdG9uZXMgaW4gdG90YWwgYXJlIHRoZXIgc3RvbmVzIGFyZSBpbiBib3hlcyBsYWJlbGVkIEwgdG8gUiAoaW5jbHVzaXZlKS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBxdWVyeSBiZWdpbm5pbmcgd2l0aCAyIG91dHB1dCB0aGUgYW5zd2VyIHRvIHRoYXQgcGFydGljdWxhciBxdWVyeS4gUXVlcmllcyBzaG91bGQgYmUgcHJvY2Vzc2VkIGluIHRoZSBvcmRlciB0aGV5IGFyZSBnaXZlbiBpbiB0aGUgaW5wdXQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d