Фермер Джон косит траву.
Он перемещает комбайн один раз в день. В день 1 он начинает в позиции
\((x_1, y_1)\) и в день \(d\) перемещается по прямой в позицию \((x_d, y_d)\),
двигаясь или горизонтально или вертикально по 2D-карте своей фермы.
То есть либо \(x_d = x_{d-1}\), либо \(y_d = y_{d-1}\). ФД чередует
в последовательные дни горизонтальные и вертикальные участки.
Он косит довольно медленно, поэтому может такое случится, что
когда он вернётся в позицию, там уже снова вырастет трава. Точнее,
если в какой-то ячейке трава была скошена в день \(d\), то она повторно
вырастет в день \(d + T\), поэтому если ФД попал в какую-то ячейку, в которой
уже был не менее, чем \(T\) днями раньше, то ему придётся снова косить там траву.
ФД хочет посчитать, сколько раз такое случится.
Подсчитайте количество раз, когда ФД проходит через ячейку, в которой он уже
Был, и там опять выросла трава. Вы должны считать только перпендикулярные
пересечения, которые определены как общая точка горизонтальных и вертикальных
сегментов, в конечной точке отрезка или нет.
ФОРМАТ ВВОДА (файл mowing.in):
Первая строка ввода содержит \(N\) (\(2 \leq N \leq 100,000\)) и \(T\)
(\(1 \leq T \leq N\), \(T\) even).
Следующие \(N\) строк описывают позицию комбайна в дни \(1 \ldots N\).
i-ая из этих строк содержит целые числа \(x_i\) \(y_i\) (неотрицательные целые
не более 1,000,000,000).
ФОРМАТ ВЫВОДА (файл mowing.out):
Выведите количество точек пересечения, описанных выше.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
8
5
6
13
3
4
|
5
|
|
2
|
5
8
10
3
11
1
|
3.0
|
|
3
|
7 2
20
25
18
8
10
3
1
|
5
|
|
4
|
7
3
5
1
6
2
14
10
|
5
|
|
5
|
5 6
......
..X..X
X..X..
......
..X...
|
16
|
|
6
|
14
NNNESWWWSSEEEE
|
2
|
|
7
|
4
0 0
0 10
1 10
1 0
|
2
|
|
8
|
4
0 0
0 10
1 10
1 0
|
2
|
|
9
|
6
N 10
E 2
S 3
W 4
S 5
E 8
|
10
|
|
10
|
7 4
0 10
10 10
10 5
3 5
3 12
6 12
6 3
|
1
|
|
11
|
1 2
1 1
1 1
1 2
|
1
1
1
|
|
12
|
2 7
3 0
5 0
NN
NWWWWWN
|
28
|