#3165. 拉格朗日插值 暂未评定

这是一道模板题。

维护一个点集 ，初始时点集为空集。下面依次进行 个操作，操作有两种：

• 1 x y：向点集中添加点 。保证点集中 互不相同。
• 2 k：输出 的值，其中 是一个次数不超过 次的函数，且经过 中所有的点。

第一行，一个整数 ，表示操作个数。

接下来 行，每行 或 个整数，描述操作。

数据保证第一个操作必定为 1 类型操作。

只有一行，一个整数，表示 的值。

样例输入

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

样例输出

3
9
12

样例解释

初始时点集 。

第一个操作 1 2 3，向点集中插入点 。此时点集 。

第二个操作 2 5，询问 的值。唯一满足次数不超过 次且经过点 的函数为 ，因此 。

第三个操作 1 4 5，向点集中插入点 。此时点集 。

第四个操作 2 5，询问 的值。唯一满足次数不超过 次且经过点 的函数为 ，因此 。

第五个操作 1 1 4，向点集中插入点 。此时点集 。

第六个操作 2 5，询问 的值。唯一满足次数不超过 次且经过点 的函数为 ，因此 。

对于 的数据，，所有 互不相同。

数据有一定梯度。