C - Spring Thief Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

問題文

N 本の桜の木があります。木 i は時刻 S_i に花が咲き、時刻 T_i に（その時点で咲いていれば）散ります。

K の倍数の時刻に雨が振り、その時点で咲いている桜の花はすべて散ります。各 i=1,2,\dots,N について、木 i の花が咲いている時間の長さを求めてください。

制約

  • 1 \leq N \leq 100
  • 1 \leq S_i < T_i \leq 10^9
  • 2 \leq K \leq 10^9
  • S_i は K の倍数でない
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N K
S_1 T_1
S_2 T_2
\vdots
S_N T_N

出力

木 i=1,2,\dots,N に対する答えを、この順に空白区切りで 1 行で出力せよ。

入力例 1

3 5
1 3
2 5
4 10

出力例 1

2 3 1
  • 木 1：時刻 1 に咲き、時刻 3 に散ります。答えは 2 です。
  • 木 2：時刻 2 に咲き、時刻 5 に散ります。答えは 3 です。
  • 木 3：時刻 4 に咲き、時刻 5 に雨が降って散ります。答えは 1 です。

Problem Statement

There are N cherry blossom trees. Tree i blooms at time S_i, but sheds its blossoms (if any) at time T_i.

It rains each time that is a multiple of K, causing all blossoms blooming at that time to shed. For each i=1,2,\dots,N, find the duration for which tree i blooms.

Constraints

  • 1 \leq N \leq 100
  • 1 \leq S_i < T_i \leq 10^9
  • 2 \leq K \leq 10^9
  • S_i is not a multiple of K.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N K
S_1 T_1
S_2 T_2
\vdots
S_N T_N

Output

Print the answers for trees i=1,2,\dots,N in one line, in this order, with spaces in between.

Sample Input 1

3 5
1 3
2 5
4 10

Sample Output 1

2 3 1
  • Tree 1: blooms at time 1 and sheds its blossoms at time 3. The answer is 2.
  • Tree 2: blooms at time 2 and sheds its blossoms at time 5. The answer is 3.
  • Tree 3: blooms at time 4 and sheds its blossoms at time 5 because of the rain. The answer is 1.