# #743. 【ZJOI2022】面条

### 题目背景

“不好了，可怜给我发信息说她降落后被拉去隔离 30 天了，没有电脑，出不了题”，绫突然收到了不幸的消息。

“那咋办？没 idea 了，编不出来了啊！” 众人慌作一团。

### 题目描述

1. 将面条对折，面条的长度会变成 $\frac{n}{2}$，第 $i$ 个位置的调料数量会变为原来第 $i$ 个位置的调料与第 $n - i + 1$ 个位置的调料数量之和，如果新面条第 $i$ 个位置的调料数量为 $b_i$，那么满足 $b_i = a_i + a_{n - i + 1}$。
2. 将面条拉回原来的长度 $n$，每个位置会变为两个位置，并且调料数量会均分，如果现在的第 $i$ 个位置的调料数量是 $a'_i$，那么 $a'_i = \frac{1}{2} \times b_{\left\lceil \frac{i}{2} \right\rceil}$。

### 输入格式

#include <bits/stdc++.h>
using namespace std;

unsigned long long rd (unsigned long long &x) {
x ^= (x << 13);
x ^= (x >> 7);
x ^= (x << 17);
return x;
}

int main () {
int test, T;
unsigned long long seed;
scanf("%d%d%llu", &test, &T, &seed);
for (int Case = 1; Case <= T; Case ++) {
int n, q, x;
long long k_max;
scanf("%d%d%d%lld", &n, &q, &x, &k_max);
vector<int> a(n + 1);
for (int i = 1; i <= n; i ++) {
scanf("%d", &a[i]);
}
for (int i = 1; i <= q; i ++) {
long long k = rd(seed) % k_max;
/∗
∗/
}
}
}

### 样例一

#### input

0 2 13
4 2 1 3
1 4 2 3
6 2 3 3
6 2 5 3 1 4



#### output

5
499122191



### 限制与约定

$1$ $500$ $500$ $500$
$2$ $2 \times {10}^6$ $2 \times {10}^6$ $10$
$3$ $2 \times {10}^6$ $2 \times {10}^6$ ${10}^{18}$ $n = 2^k$
$4$ $50$ $50$ ${10}^{18}$
$5 \sim 6$ $150$ $150$ ${10}^{18}$
$7$ $2 \times {10}^6$ $2 \times {10}^6$ ${10}^{18}$ $n = 98304$
$8 \sim 9$ $500$ $500$ ${10}^{18}$
$10 \sim 11$ $5 \times {10}^3$ $2 \times {10}^6$ ${10}^{18}$
$12 \sim 13$ $2 \times {10}^6$ $50$ ${10}^{18}$
$14 \sim 16$ ${10}^6$ ${10}^5$ ${10}^{18}$
$17 \sim 18$ $2 \times {10}^6$ $2 \times {10}^7$ ${10}^{18}$
$19 \sim 20$ $2 \times {10}^6$ $5 \times {10}^7$ ${10}^{18}$