신기한 물체

길을 걷던 한 사람이 신기한 물체를 발견했다. 이 물체의 왼쪽에는 처음에 모두 비어 있는 박스 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,000
• 1 <= 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로 시작하는 명령마다 해당 구간의 돌 개수를 한 줄에 하나씩 출력한다.