E - Goal Achievement Training Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 433 点

問題文

高橋君はマラソン大会に向けて、合計 P km のトレーニングを達成することを目標にしています。高橋君はすでに大会前の合宿で D km を走っています。

N 日分の日々のトレーニング記録があり、i 日目の走行距離は A_i km です。

コーチから Q 件の確認依頼が届きました。各確認依頼では、指定された期間内の連続する日々のトレーニングと合宿分の走行距離を合わせて、ちょうど目標の P km に一致するような連続区間がいくつあるかを調べます。

具体的には、i 番目の確認依頼では L_i 日目から R_i 日目までの記録を対象とし、次の条件をともに満たす整数組 (l, r) を考えます。

  • L_i \leq l \leq r \leq R_i
  • D + A_l + A_{l+1} + \cdots + A_r = P

このような整数組 (l, r) の個数を C_i とします。

また、すべてのそのような整数組について、期間の日数 r - l + 1 の総和を T_i とします（条件を満たす整数組が存在しない場合は T_i = 0 とします）。

各確認依頼について、C_i と T_i を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 10^5
  • 1 \leq P \leq 10^9
  • 0 \leq D \leq P
  • 1 \leq A_i \leq 10^4
  • 1 \leq L_i \leq R_i \leq N
  • 入力はすべて整数である

入力

N Q P D
A_1 A_2 \ldots A_N
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q
  • 1 行目には、日数を表す N 、確認依頼の個数を表す Q 、目標距離を表す P 、合宿での走行距離を表す D が、スペース区切りで与えられる。
  • 2 行目には、各日の走行距離を表す A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
  • 続く Q 行には、確認依頼の内容が与えられる。
  • 2 + i 行目には、i 番目の確認依頼で対象とする日の範囲を表す L_i と R_i が、スペース区切りで与えられる。

出力

Q 行出力してください。

i 行目には、i 番目の確認依頼に対する C_i と T_i を、この順にスペース区切りで出力してください。

入力例 1

5 3 10 3
2 5 1 6 1
1 5
1 3
3 5

出力例 1

3 6
1 2
2 4

入力例 2

4 4 20 5
1 2 3 4
1 4
1 2
2 3
3 4

出力例 2

0 0
0 0
0 0
0 0

入力例 3

12 6 15 5
3 7 2 8 5 5 1 9 4 6 10 2
1 12
1 4
5 8
7 11
3 10
11 12

出力例 3

6 11
2 4
2 4
3 5
4 8
1 1

入力例 4

40 20 50 20
5 10 15 20 5 5 10 10 20 1 29 30 2 8 12 18 7 23 4 6 14 16 9 11 3 27 13 17 25 5 10 20 15 15 1 2 3 24 6 9
1 40
1 10
5 15
10 20
12 12
11 12
13 18
20 30
25 35
30 40
2 25
7 32
15 28
3 37
18 22
21 24
26 27
33 38
34 40
1 1

出力例 4

16 37
4 12
4 9
4 7
1 1
1 1
2 4
4 8
5 10
4 10
8 18
10 19
5 10
13 28
1 2
1 2
0 0
2 6
2 6
0 0

入力例 5

1 1 1000000000 1000000000
1
1 1

出力例 5

0 0

Score : 433 pts

Problem Statement

Takahashi is aiming to achieve a total of P km of training for a marathon. Takahashi has already run D km during a training camp before the race.

There are training records for N days, and the running distance on day i is A_i km.

Q verification requests have arrived from the coach. For each verification request, the task is to find how many contiguous subarrays of consecutive days within a specified period, combined with the training camp distance, exactly match the target of P km.

Specifically, for the i-th verification request, consider the records from day L_i to day R_i, and find all integer pairs (l, r) satisfying both of the following conditions:

  • L_i \leq l \leq r \leq R_i
  • D + A_l + A_{l+1} + \cdots + A_r = P

Let C_i be the number of such integer pairs (l, r).

Also, let T_i be the sum of the number of days r - l + 1 over all such integer pairs (if no integer pairs satisfy the conditions, then T_i = 0).

For each verification request, find C_i and T_i.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 10^5
  • 1 \leq P \leq 10^9
  • 0 \leq D \leq P
  • 1 \leq A_i \leq 10^4
  • 1 \leq L_i \leq R_i \leq N
  • All inputs are integers

Input

N Q P D
A_1 A_2 \ldots A_N
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q
  • The first line contains N representing the number of days, Q representing the number of verification requests, P representing the target distance, and D representing the distance run during the training camp, separated by spaces.
  • The second line contains A_1, A_2, \ldots, A_N representing the running distance for each day, separated by spaces.
  • The following Q lines contain the verification requests.
  • The (2 + i)-th line contains L_i and R_i representing the range of days for the i-th verification request, separated by spaces.

Output

Output Q lines.

On the i-th line, output C_i and T_i for the i-th verification request, in this order, separated by a space.

Sample Input 1

5 3 10 3
2 5 1 6 1
1 5
1 3
3 5

Sample Output 1

3 6
1 2
2 4

Sample Input 2

4 4 20 5
1 2 3 4
1 4
1 2
2 3
3 4

Sample Output 2

0 0
0 0
0 0
0 0

Sample Input 3

12 6 15 5
3 7 2 8 5 5 1 9 4 6 10 2
1 12
1 4
5 8
7 11
3 10
11 12

Sample Output 3

6 11
2 4
2 4
3 5
4 8
1 1

Sample Input 4

40 20 50 20
5 10 15 20 5 5 10 10 20 1 29 30 2 8 12 18 7 23 4 6 14 16 9 11 3 27 13 17 25 5 10 20 15 15 1 2 3 24 6 9
1 40
1 10
5 15
10 20
12 12
11 12
13 18
20 30
25 35
30 40
2 25
7 32
15 28
3 37
18 22
21 24
26 27
33 38
34 40
1 1

Sample Output 4

16 37
4 12
4 9
4 7
1 1
1 1
2 4
4 8
5 10
4 10
8 18
10 19
5 10
13 28
1 2
1 2
0 0
2 6
2 6
0 0

Sample Input 5

1 1 1000000000 1000000000
1
1 1

Sample Output 5

0 0