#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define ull unsigned ll
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define f0(i,n) for(int i=0;i<n;i++)
#define f1(i,n) for(int i=1;i<=n;i++)
#define fz(i,a,n,z) for(int i=a;i<n;i+=z)
#define rep(i,a,n,z) for(int i=a;i>n;i-=z)
#define faster ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file(name) freopen(name".inp","r",stdin);freopen(name".out","w",stdout);
const int N = 1e6 + 5;
// ll max_uocLe(ll n) {
// if (n % 2 == 1) return n;
// ll res = 1;
// for (ll i = 2; i <= sqrt(n); ++i) {
// if (n % i == 0) {
// if (i % 2 == 1) {
// res = max(res, i);
// }
// if ((n / i) % 2 == 1) {
// res = max(res, n / i);
// }
// }
// }
// return res;
// }
// ll pre[N];
// ll to = 0, z[200001], n, k, i, m, a[200001], x[200001], y[200001], d[200001] = {};
int main() {
faster
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// cin >> n >> m;
// for (i = 1; i <= n; i++) {cin >> a[i]; pre[i] = pre[i - 1] + a[i] + a[max_uocLe(i)];}
// for (i = 1; i <= n; i++)
// {
// k = i;
// while (k % 2 == 0) k /= 2;
// d[i] = k;
// }
// bool check = true;
// for (i = 1; i <= m; ++i) {
// cin >> x[i] >> y[i] >> z[i];
// if (x[i] == 1) {
// check = false;
// }
// }
// if (check == false) {
// for (ll it = 1; it <= m; ++it)
// {
// if (x[it] == 1)
// {
// swap(a[y[it]], z[it]);
// }
// else
// {
// to = 0;
// for (i = y[it]; i <= z[it]; i++)
// {
// to += a[i] + a[d[i]];
// }
// cout << to << "\n";
// }
// }
// }
// else {
// for (ll it = 1; it <= m; ++it) {
// cout << pre[z[it]] - pre[y[it] - 1] << "\n";
// }
// }
}
/*-----------------------END-----------------------*/
I3ByYWdtYSBHQ0Mgb3B0aW1pemUoIk8zLHVucm9sbC1sb29wcyIpCiNpbmNsdWRlPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgZmkgZmlyc3QKI2RlZmluZSBzZSBzZWNvbmQKI2RlZmluZSBsbCBsb25nIGxvbmcKI2RlZmluZSB1bGwgdW5zaWduZWQgbGwKI2RlZmluZSBzeih4KSAoaW50KSh4KS5zaXplKCkKI2RlZmluZSBhbGwoeCkgKHgpLmJlZ2luKCksKHgpLmVuZCgpCiNkZWZpbmUgZjAoaSxuKSBmb3IoaW50IGk9MDtpPG47aSsrKQojZGVmaW5lIGYxKGksbikgZm9yKGludCBpPTE7aTw9bjtpKyspCiNkZWZpbmUgZnooaSxhLG4seikgZm9yKGludCBpPWE7aTxuO2krPXopCiNkZWZpbmUgcmVwKGksYSxuLHopIGZvcihpbnQgaT1hO2k+bjtpLT16KQojZGVmaW5lIGZhc3RlciBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTtjaW4udGllKDApO2NvdXQudGllKDApOwojZGVmaW5lIGZpbGUobmFtZSkgZnJlb3BlbihuYW1lIi5pbnAiLCJyIixzdGRpbik7ZnJlb3BlbihuYW1lIi5vdXQiLCJ3IixzdGRvdXQpOwpjb25zdCBpbnQgTiA9IDFlNiArIDU7Ci8vIGxsIG1heF91b2NMZShsbCBuKSB7Ci8vICAgICBpZiAobiAlIDIgPT0gMSkgcmV0dXJuIG47Ci8vICAgICBsbCByZXMgPSAxOwovLyAgICAgZm9yIChsbCBpID0gMjsgaSA8PSBzcXJ0KG4pOyArK2kpIHsKLy8gICAgICAgICBpZiAobiAlIGkgPT0gMCkgewovLyAgICAgICAgICAgICBpZiAoaSAlIDIgPT0gMSkgewovLyAgICAgICAgICAgICAgICAgcmVzID0gbWF4KHJlcywgaSk7Ci8vICAgICAgICAgICAgIH0KLy8gICAgICAgICAgICAgaWYgKChuIC8gaSkgJSAyID09IDEpIHsKLy8gICAgICAgICAgICAgICAgIHJlcyA9IG1heChyZXMsIG4gLyBpKTsKLy8gICAgICAgICAgICAgfQovLyAgICAgICAgIH0KLy8gICAgIH0KLy8gICAgIHJldHVybiByZXM7Ci8vIH0KLy8gbGwgcHJlW05dOwovLyBsbCB0byA9IDAsIHpbMjAwMDAxXSwgbiwgaywgaSwgbSwgYVsyMDAwMDFdLCB4WzIwMDAwMV0sIHlbMjAwMDAxXSwgZFsyMDAwMDFdID0ge307CmludCBtYWluKCkgewogICAgZmFzdGVyCiAgICBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKICAgIGNpbi50aWUoMCk7CiAgICBjb3V0LnRpZSgwKTsKICAgIC8vIGNpbiA+PiBuID4+IG07CiAgICAvLyBmb3IgKGkgPSAxOyBpIDw9IG47IGkrKykge2NpbiA+PiBhW2ldOyBwcmVbaV0gPSBwcmVbaSAtIDFdICsgYVtpXSArIGFbbWF4X3VvY0xlKGkpXTt9CiAgICAvLyBmb3IgKGkgPSAxOyBpIDw9IG47IGkrKykKICAgIC8vIHsKICAgIC8vICAgICBrID0gaTsKICAgIC8vICAgICB3aGlsZSAoayAlIDIgPT0gMCkgayAvPSAyOwogICAgLy8gICAgIGRbaV0gPSBrOwoKCiAgICAvLyB9CiAgICAvLyBib29sIGNoZWNrID0gdHJ1ZTsKICAgIC8vIGZvciAoaSA9IDE7IGkgPD0gbTsgKytpKSB7CiAgICAvLyAgICAgY2luID4+IHhbaV0gPj4geVtpXSA+PiB6W2ldOwogICAgLy8gICAgIGlmICh4W2ldID09IDEpIHsKICAgIC8vICAgICAgICAgY2hlY2sgPSBmYWxzZTsKICAgIC8vICAgICB9CiAgICAvLyB9CiAgICAvLyBpZiAoY2hlY2sgPT0gZmFsc2UpIHsKICAgIC8vICAgICBmb3IgKGxsIGl0ID0gMTsgaXQgPD0gbTsgKytpdCkKICAgIC8vICAgICB7CiAgICAvLyAgICAgICAgIGlmICh4W2l0XSA9PSAxKQogICAgLy8gICAgICAgICB7CiAgICAvLyAgICAgICAgICAgICBzd2FwKGFbeVtpdF1dLCB6W2l0XSk7CiAgICAvLyAgICAgICAgIH0KICAgIC8vICAgICAgICAgZWxzZQogICAgLy8gICAgICAgICB7CiAgICAvLyAgICAgICAgICAgICB0byA9IDA7CiAgICAvLyAgICAgICAgICAgICBmb3IgKGkgPSB5W2l0XTsgaSA8PSB6W2l0XTsgaSsrKQogICAgLy8gICAgICAgICAgICAgewogICAgLy8gICAgICAgICAgICAgICAgIHRvICs9IGFbaV0gKyBhW2RbaV1dOwogICAgLy8gICAgICAgICAgICAgfQogICAgLy8gICAgICAgICAgICAgY291dCA8PCB0byA8PCAiXG4iOwogICAgLy8gICAgICAgICB9CiAgICAvLyAgICAgfQogICAgLy8gfQogICAgLy8gZWxzZSB7CiAgICAvLyAgICAgZm9yIChsbCBpdCA9IDE7IGl0IDw9IG07ICsraXQpIHsKICAgIC8vICAgICAgICAgY291dCA8PCBwcmVbeltpdF1dIC0gcHJlW3lbaXRdIC0gMV0gPDwgIlxuIjsKICAgIC8vICAgICB9CiAgICAvLyB9Cgp9CgovKi0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tRU5ELS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0qLwoKCgoKCg==