背景

Xlw6friend 在做奇妙的思维题目。

题目描述

有 $n$ 堆不同的数，每堆内有 $b_i$ 个数，它们值相同且均为 $a_i$。不保证两两堆的值不同。

给定一个正整数 $k$（$k \geq 2$），你可以对每个数进行两种操作：

• 将一个数乘以 $k$；
• 将一个数除以 $k$ 并向下取整。

Xlw6friend 会给出 $q$ 次修改。每次给定两个整数 $p_i$, $x_i$，表示他要将 $a_{p_i}$ 改为 $x_i$。修改后不保证两两堆的值不同。

每次修改后，你需要再次计算最少通过多少次操作可以将这些数的值变为全部相同，以及在这个前提下，这个最终的值最大是多少。

输入格式

第一行两个正整数 $n$, $k$。

接下来 $n$ 行，每行两个正整数 $a_i$, $b_i$。

第 $n + 2$ 行一个整数 $q$。

接下来 $q$ 行，每行两个正整数数 $p_i$, $x_i$。

输出格式

输出共 $q+1$ 行。

每行两个数，表示最小操作数和这个前提下最终的数的最大值。

3 2
2 1
4 1
8 1
0

2 4

3 2
3 1
5 1
6 1
0

5 1

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

5 1
4 2
5 2
2 4

3 3
1 50
46 50
34 11
3
1 33
1 29
3 27

183 1
322 3
322 3
311 9

提示

数据规模与约定：

本题采用捆绑测试。

• 特殊性质 A: 保证数据随机生成。

• 特殊性质 B: 保证 $a_i,x_i < k$。

对于 $100 \%$ 的数据，保证 $1 \leq p_i \leq n, 0 \leq a_i,b_i,x_i \leq 5 \times 10^5$，$2 \leq k \leq 5 \times 10^5$, $0 \leq q \leq 5 \times 10^5$。