Use FFT

内存限制: 128M   时间限制: 1S

题目描述


输入

输出

样例输入

1 1 0 2
1 2
3 4
1 1 1 2
1 2
3 4
2 3 0 5
1 2 999999999
1 2 3 1000000000

样例输出

21
18
5