Cubes

题意翻译

### 题目描述 一次，Vasya 和 Petya 用 $m$ 个方块搭建了一个图形。这些方块上被标号为 $0$ 到 $m - 1$。以地面为 $x$ 轴，以垂直向上为正方向建立 $y$ 轴。我们用每个方块左下角的坐标表示它的位置。每个方块的坐标都是整数。 这个图形原本是稳定的。这是指对于每个不是贴在地上的方块，它下方必然存在一个与它相交于一条边或一个角的方块支撑着它。更形式化地说，对于每个方块 $(x, y)$，要么有 $y = 0$，要么存在方块 $(x - 1, y - 1)$，$(x, y - 1)$ 或 $(x + 1, y - 1)$。 现在他们想要拆除这个图形，并吧这些方块一列排开。在一步操作中，一个方块会从图形中被移除，然后被放到已移除的所有方块的最右侧。他们移除方块时，图形仍然是稳定的。 为了使得这个过程更加有意思，Vasya 和 Petya 决定进行如下游戏。他们轮流从图形中取走方块。显然会发现，在图形被完全拆除后，所有方块的编号连起来形成了一个 $m$ 进制的数（可能有前导 $0$）。Vasya 希望这个数尽可能大，而 Petya 正相反，希望这个数尽可能小。Vasya 先手。 你的任务是在两人都采取最优策略的情况下，确定最终形成的数字是多少。输出答案对 $10 ^ 9 + 9$ 取模的结果。 ### 输入格式 第一行输入一个整数 $m ~ (2 \le m \le 10 ^ 5)$。 接下来 $m$ 行，每行输入两个整数 $x_i, y_i ~ (-10 ^ 9 \le x_i \le 10 ^ 9; 0 \le y_i \le 10 ^ 9)$，按标号递增顺序给出每个方块的坐标。 保证输入的原图是稳定的，且没有两个方块位于相同的位置。 ### 输出格式 输出一行，表示问题的答案。

题目描述

Once Vasya and Petya assembled a figure of $ m $ cubes, each of them is associated with a number between $ 0 $ and $ m-1 $ (inclusive, each number appeared exactly once). Let's consider a coordinate system such that the $ OX $ is the ground, and the $ OY $ is directed upwards. Each cube is associated with the coordinates of its lower left corner, these coordinates are integers for each cube. The figure turned out to be stable. This means that for any cube that is not on the ground, there is at least one cube under it such that those two cubes touch by a side or a corner. More formally, this means that for the cube with coordinates $ (x,y) $ either $ y=0 $ , or there is a cube with coordinates $ (x-1,y-1) $ , $ (x,y-1) $ or $ (x+1,y-1) $ . Now the boys want to disassemble the figure and put all the cubes in a row. In one step the cube is removed from the figure and being put to the right of the blocks that have already been laid. The guys remove the cubes in such order that the figure remains stable. To make the process more interesting, the guys decided to play the following game. The guys take out the cubes from the figure in turns. It is easy to see that after the figure is disassembled, the integers written on the cubes form a number, written in the $ m $ -ary positional numerical system (possibly, with a leading zero). Vasya wants the resulting number to be maximum possible, and Petya, on the contrary, tries to make it as small as possible. Vasya starts the game. Your task is to determine what number is formed after the figure is disassembled, if the boys play optimally. Determine the remainder of the answer modulo $ 10^{9}+9 $ .

输入输出格式

输入格式

The first line contains number $ m $ ( $ 2<=m<=10^{5} $ ). The following $ m $ lines contain the coordinates of the cubes $ x_{i},y_{i} $ ( $ -10^{9}<=x_{i}<=10^{9} $ , $ 0<=y_{i}<=10^{9} $ ) in ascending order of numbers written on them. It is guaranteed that the original figure is stable. No two cubes occupy the same place.

输出格式

In the only line print the answer to the problem.

输入输出样例

输入样例 #1

3
2 1
1 0
0 1

输出样例 #1

19

输入样例 #2

5
0 0
0 1
0 2
0 3
0 4

输出样例 #2

2930