Little Q 正在和 Tangjz 一起吃火锅。锅里有 $n$ 盘肉，编号为 $1, 2, \dots, n$。第 $i$ 盘肉将在时刻 $a_i$ 煮熟，Little Q 吃完它需要 $b_i$ 的时间。Little Q 可以在任何时刻 $t \ge a_i$ 开始吃第 $i$ 盘肉，并且他必须连续吃完它，直到时刻 $t + b_i$。Little Q 不能同时吃超过一盘肉。

Little Q 被称为“火锅之王”，他想在 Tangjz 面前炫耀，尽快吃完 $k$ 盘肉。计时从时刻 $0$ 开始。请编写一个程序，对于每个 $k$ ($1 \le k \le n$)，独立地找出 $k$ 盘肉以及吃它们的顺序，使得吃完 $k$ 盘肉的总时间最小。注意，任何等待时间也包含在答案中。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10\,000$)，表示测试用例的数量。对于每个测试用例： 第一行包含一个整数 $n$ ($1 \le n \le 300\,000$)，表示肉的盘数。 接下来的 $n$ 行，每行包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i, b_i \le 10^9$)，描述一盘肉。 保证所有测试用例的 $n$ 之和不超过 $1\,000\,000$。

输出格式

对于每个测试用例，输出一行，包含 $n$ 个整数，其中第 $k$ 个整数 ($1 \le k \le n$) 表示 Little Q 吃完 $k$ 盘肉所需的最短总时间。

样例

输入 1

1
5
1 2
4 6
3 5
4 2
3 2

输出 1

3 5 7 12 18