문제 124
몫의 세 가지 합
네 정수 $N$, $M$, $A$, $B$가 주어진다. $0\le i<N$인 정수 $i$에 대해 $f(i)=\left\lfloor\dfrac{Ai+B}{M}\right\rfloor$라 할 때, 다음 세 합을 구해 보자.
\[ \sum_{i=0}^{N-1}f(i),\qquad \sum_{i=0}^{N-1}i f(i),\qquad \sum_{i=0}^{N-1}f(i)^2. \]
입력
첫 번째 줄에 테스트 케이스의 수를 의미하는 정수 $T$가 주어진다. $(1 \le T \le 20\,000)$
두 번째 줄부터 $T$개의 줄에 걸쳐 네 정수 $N$, $M$, $A$, $B$가 공백으로 구분되어 주어진다. $(0 \le N \le 10^6; 1 \le M \le 10^9; 0 \le A, B \le 10^9)$ 각 줄이 하나의 테스트 케이스이다.
출력
각 테스트 케이스마다 세 합을 본문에 제시된 순서대로 공백으로 구분하여 한 줄에 출력한다. 답은 부호 있는 $128$비트 정수의 범위 안에 든다.
예제 입력 1
5 0 7 3 5 5 1 0 0 5 3 2 1 1000000 1 1000000000 999999999 1 1000000000 0 1000000000
예제 출력 1
0 0 0 0 0 0 7 21 15 500000499999999000000 333333333332999500000500000 333333833333498999999000000001000000 1 0 1