题目描述

有 $n$ 个人，你需要给他们购买巧克力，每买一个巧克力附着一个门票，还有 $m$ 种交换关系：

• 使用 $a_i$ 张门票换取 $b_i$ 个巧克力，这 $b_i$ 个巧克力附着 $b_i$ 个门票。

试问对于 $1\le i \le n$，为了给 $i$ 个人巧克力，你在初始的时候需要最少购买多少巧克力？

输入格式

一行两个整数 $n,m$，表示人数和交换关系数。

以下 $m$ 行，每行两个整数 $a_i,b_i$，含义如题所示。

输出格式

$n$ 行，第 $i$ 行一个整数 $x$，表示给 $i$ 个人巧克力最少需要购买的巧克力数量。

2 12
3 1
5 2

1
2
3
3
4
5
5
6
6
7
8
8

1 10
4 3

1
2
3
4
4
4
4
5
5
5

3 10
3 1
5 3
4 2

1
2
3
3
4
4
5
5
5
6

提示

【样例解释】

对于样例 $1$，例如，购买 $6$ 块巧克力，使用以下交换规则，可以获得 $9$ 块巧克力。

• 首先，有 $6$ 块巧克力和 $6$ 张门票。

• 使用第二种交换规则。 给出 $5$ 张门票，得到 $2$ 块巧克力和 $2$ 张门票。 目前有 $8$ 块巧克力和 $3$ 张门票。

• 使用第一种交换规则。 给出 $3$ 张门票，得到 $1$ 块巧克力和 $1$ 张门票。 目前有 $9$ 块巧克力和 $1$ 张门票。

【数据规模与约定】

对于全部数据，均有 $1\le n \le 500,1\le m \le 100000,1 \le b_i<a_i<m$。

• Subtask $1$（$15$ pts）：$m\le 500,n=1$。
• Subtask $2$（$15$ pts）：$m\le 500$，且 $a_i-b_i$ 均相等。
• Subtask $3$（$30$ pts）：$m\le 500$。
• Subtask $4$（$40$ pts）：无特殊限制。