신기한 물체
시간 제한8초메모리 제한128 MB
박스 X를 [L,R] 범위에서 ((X-L+1)*A) mod B 값으로 덮어쓰는 갱신을 처리하며, 최대 10^9개 박스와 5만 개 연산으로 구간 합 질의에 답해야 합니다.
문제
길을 걷던 한 사람이 신기한 물체를 발견했다. 이 물체의 왼쪽에는 처음에 모두 비어 있는 박스 N개가 일렬로 놓여 있다.
물체는 네 정수 L, R, A, B를 입력으로 받는다. 실행 버튼을 누르면, L번 박스부터 R번 박스까지의 돌 개수를 다음 규칙에 따라 바꾼다.
L번 박스에는 A mod B개의 돌을 넣는다. L+1번 박스에는 (2*A) mod B개의 돌을 넣는다. 일반적으로 L <= X <= R인 X번 박스의 돌 개수는 ((X-L+1)*A) mod B가 된다.
여러 번의 명령이 주어질 때, 구간에 들어 있는 돌의 총개수를 묻는 명령의 답을 구하시오.
입력
첫째 줄에 박스의 수 N과 쿼리의 수 Q가 주어진다.
1 <= N <= 1,000,000,0001 <= Q <= 50,000
다음 Q개의 줄에는 명령이 하나씩 주어진다.
1 L R A B:L번부터R번 박스까지 위 규칙으로 돌의 개수를 바꾼다. (1 <= L <= R <= N,1 <= A, B <= 1,000,000)2 L R:L번부터R번 박스까지 들어 있는 돌의 총개수를 묻는다. (1 <= L <= R <= N)
모든 구간은 양 끝을 포함한다.
출력
2로 시작하는 명령마다 해당 구간의 돌 개수를 한 줄에 하나씩 출력한다.