U289544 蜗蜗棋

蜗蜗最近沉迷上了`蜗蜗棋`。 `蜗蜗棋`里有一颗棋子，一开始出现在**数轴**上等于 $x$ 的位置。

`蜗蜗棋`里有一颗棋子，一开始出现在**数轴**上等于 $x$ 的位置。 对于每一步，假设当前棋子的位置为 $c$，如果 $c

**注意：本题有多组询问。** 第一行一个整数 $T$ 表示询问组数。 对于每组询问，一行五个整数 $x,y,z,k,s$。

共 $T$ 行。 对于每组数据，输出**一行一个**整数表示棋子最后的位置。

### 更多样例 由于数据过大，样例#5、#6已放在附件内。 ### 数据范围 共 20 组数据。 对于 30% 的数据，保证 $1 \le T \le 100$, $1 \le s \le 10^5$。 **对于 100% 的数据**，保证 $1 \le T \le 10^5$, $1 \le x,y,z,k,s \le 10^9$。 提示：数据范围较大，请使用较高效的方法，例如$O(Tlogs)$的[二分](https://www.luogu.com.cn/training/111)法。 下列是不同方法的时间复杂度: |方法|时间复杂度|极限情况|可行|能获得的分数| |:-:|:-:|:-:|:-:|:-:| |暴力[模拟](https://www.luogu.com.cn/training/106)|$O(Ts)$|$10^5 \times 10^9 = 10^{14}$|No|30(后面14个点TLE)| |**[二分](https://www.luogu.com.cn/training/111)**|$O(T\log s)$|$10^5 \times \log_2(10^9) \approx 3 \times 10^6 $|**Yes**|**100**| ### 来源 Daimayuan Online Judge 原题链接: [oj.daimayuan.top](http://oj.daimayuan.top/course/36/problem/1246) 提供人: [](https://www.luogu.com.cn/user/819328#practice)