该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

TG T3 log.cpp

Description

给定一个 $n$ 次多项式 $A=a_0x^0+a_1x^1+ \dots + a_nx^n$。

现给定 $x$，并进行 $q$ 次操作，每次将某个系数 $a_i$ 变为 $a_i+1$ 或 $a_i-1$。

每次操作后，你需要求出 $\lfloor \log_xA \rfloor$ 的值。

保证在操作过程中，$A$ 的值永远大于 $0$。

log 是什么？

Format

Input

第一行三个正整数 $n,q,x$，意义见上。

第二行 $n+1$ 个整数，表示多项式的系数。

接下来 $q$ 行，每行两个数 $op,i$，若 $op=0$，则表示将 $a_i+1$；若 $op=1$，则表示将 $a_i-1$。

Output

共 $q$ 行，每行一个数表示答案。

Samples

2 3 3
1 2 2
0 0
0 0
1 0

2
3
2

样例 2 参见附件 log02.in\log02.ans。

Explanation

Sample 1 Explanation

给定的多项式 $A=2x^2+2x+1$。

第一次操作后，多项式变为 $2x^2+2x+2$。

当 $x=3$ 时，多项式的值为 $2\times 3^2+2\times 3+2=26$。$\lfloor \log_326 \rfloor=\lfloor2.9656\dots \rfloor=2$。

Limitation

对于 $10\%$ 的数据，保证 $1 \le n,q \le 10$，$2 \le x,a_i \le 10$。

对于 $40\%$ 的数据，保证 $1 \le n,q \le 10^3$，$2 \le x,a_i \le 10^9$。

对于 $100\%$ 的数据，保证 $1 \le n,q \le 5\times 10^5$，$2 \le x,a_i \le 10^9$。

时空限制：2000ms/512MiB。