Description

你需要维护一个映射 $f:[0,2^{64})\to[0,2^{64})$，初始 $\forall x\in [0,2^{64}),f(x)=0$。

有 $n$ 次操作，每次操作给出二元组 $(x,y)$，表示查询 $f(x)$ 的值，之后 $f(x)\gets y$。

Input Format

第一行，一个正整数 $n$。

接下来 $n$ 行，每行两个整数 $x,y$ 描述一次操作。

Output Format

为了减少输出量，设第 $i$ 次操作的答案为 $ans_i$，你只需要输出 $\sum_{i=1}^ni\times ans_i$ 对 $2^{64}$ 取模的结果。

5
0 4
0 998244353
1000000000000000000 20120712
1000000000000000000 1000000000000000000
1000000000000000000 998244353

5000000000080482856

Hint

样例的 $ans$ 分别为：$0,4,0,20120712,1000000000000000000$。

对于 $100\%$ 的数据，$1\le n \le 5\times 10^6,0\le x,y<2^{64}$。

子任务 $0\sim 3$ 的数据生成方式较为随机，子任务 $4$ 是针对 unordered_map，gp_hash_table，cc_hash_table 和一些错误的哈希方式等的 hack。

如果你认为你的代码复杂度正确却没有通过，记得使用快速读入。