#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
template<class T, class T2> inline void chkmax(T &x, const T2 &y) { if(x < y) x = y; }
template<class T, class T2> inline void chkmin(T &x, const T2 &y) { if(x > y) x = y; }
const int MAXN = (1 << 20);
int gcd(int a, int b) { return (a == 0 || b == 0) ? (a + b) : (__gcd(a, b)); }
struct segment_tree
{
struct node
{
int64_t sum, lazy;
node() {sum = 0; lazy = 0;}
node(int64_t val)
{
sum = val;
lazy = 0;
}
};
node temp, broken;
node merge(node l, node r)
{
temp.sum = l.sum + r.sum;
temp.lazy = 0;
return temp;
}
node tr[4 * MAXN];
void push(int l, int r, int idx)
{
if(tr[idx].lazy)
{
tr[idx].sum = (r - l + 1) * tr[idx].lazy;
if(l != r)
{
tr[2 * idx + 1].lazy = tr[idx].lazy;
tr[2 * idx + 2].lazy = tr[idx].lazy;
}
tr[idx].lazy = 0;
}
}
void init(int l, int r, int idx)
{
if(l == r)
{
tr[idx] = node(0);
return;
}
int mid = (l + r) >> 1;
init(l, mid, 2 * idx + 1);
init(mid + 1, r, 2 * idx + 2);
tr[idx] = merge(tr[2 * idx + 1], tr[2 * idx + 2]);
}
void update(int qL, int qR, int val, int l, int r, int idx)
{
push(l, r, idx);
if(qL > r || l > qR)
return;
if(qL <= l && r <= qR)
{
tr[idx].lazy = val;
push(l, r, idx);
return;
}
int mid = (l + r) >> 1;
update(qL, qR, val, l, mid, 2 * idx + 1);
update(qL, qR, val, mid + 1, r, 2 * idx + 2);
tr[idx] = merge(tr[2 * idx + 1], tr[2 * idx + 2]);
}
node query(int qL, int qR, int l, int r, int idx)
{
push(l, r, idx);
if(l > qR || r < qL)
return broken;
if(qL <= l && r <= qR)
return tr[idx];
int mid = (l + r) >> 1;
return merge(query(qL, qR, l, mid, 2 * idx + 1), query(qL, qR, mid + 1, r, 2 * idx + 2));
}
};
segment_tree sum_t;
struct node
{
int g;
node() { g = 0; }
node(int val) { g = val; }
};
int a[MAXN];
node temp, broken;
node merge(node l, node r)
{
temp.g = gcd(l.g, r.g);
return temp;
}
int bound_L[MAXN], bound_R[MAXN];
struct segment_tree_gcd
{
node tr[4 * MAXN];
void init(int l, int r, int idx)
{
bound_L[idx] = l;
bound_R[idx] = r;
if(l == r)
{
tr[idx] = node(a[l]);
return;
}
int mid = (l + r) >> 1;
init(l, mid, 2 * idx + 1);
init(mid + 1, r, 2 * idx + 2);
tr[idx] = merge(tr[2 * idx + 1], tr[2 * idx + 2]);
}
void update(int pos, int val, int l, int r, int idx)
{
if(l > pos || r < pos)
return;
if(l == r && l == pos)
{
tr[idx].g = val;
return;
}
int mid = (l + r) >> 1;
update(pos, val, l, mid, 2 * idx + 1);
update(pos, val, mid + 1, r, 2 * idx + 2);
tr[idx] = merge(tr[2 * idx + 1], tr[2 * idx + 2]);
}
void get_nodes(int qL, int qR, int l, int r, int idx, vector<int> &li)
{
if(l > qR || r < qL) return;
if(qL <= l && r <= qR)
{
li.push_back(idx);
return;
}
int mid = (l + r) >> 1;
get_nodes(qL, qR, l, mid, 2 * idx + 1, li);
get_nodes(qL, qR, mid + 1, r, 2 * idx + 2, li);
}
int get_left(int l, int r, int idx, int X)
{
if(l == r) return l;
int mid = (l + r) >> 1, new_gcd = gcd(X, tr[2 * idx + 2].g);
if(new_gcd == 1) return get_left(mid + 1, r, 2 * idx + 2, X);
else return get_left(l, mid, 2 * idx + 1, new_gcd);
}
int get_left_same(int l, int r, int idx, int X)
{
if(l == r) return l;
int mid = (l + r) >> 1, new_gcd = gcd(X, tr[2 * idx + 2].g);
if(new_gcd != X) return get_left_same(mid + 1, r, 2 * idx + 2, X);
else return get_left_same(l, mid, 2 * idx + 1, new_gcd);
}
int get_right(int l, int r, int idx, int X)
{
if(l == r) return l;
int mid = (l + r) >> 1, new_gcd = gcd(X, tr[2 * idx + 1].g);
if(new_gcd == 1) return get_right(l, mid, 2 * idx + 1, X);
else return get_right(mid + 1, r, 2 * idx + 2, new_gcd);
}
};
int n;
segment_tree_gcd t;
int get_left(int pos)
{
vector<int> li;
t.get_nodes(1, pos, 1, n, 0, li);
reverse(li.begin(), li.end());
int c_gcd = 0;
for(int it: li)
{
int prv_gcd = c_gcd;
c_gcd = gcd(c_gcd, t.tr[it].g);
if(c_gcd == 1) return t.get_left(bound_L[it], bound_R[it], it, prv_gcd);
}
return 0;
}
int get_right(int pos)
{
vector<int> li;
t.get_nodes(pos, n, 1, n, 0, li);
int c_gcd = 0;
for(int it: li)
{
int prv_gcd = c_gcd;
c_gcd = gcd(c_gcd, t.tr[it].g);
if(c_gcd == 1) return t.get_right(bound_L[it], bound_R[it], it, prv_gcd);
}
return n + 1;
}
int get_left_equal(int pos, int G)
{
vector<int> li;
t.get_nodes(1, pos, 1, n, 0, li);
reverse(li.begin(), li.end());
int c_gcd = G;
for(int it: li)
{
int prv_gcd = c_gcd;
c_gcd = gcd(c_gcd, t.tr[it].g);
if(c_gcd < G) return t.get_left_same(bound_L[it], bound_R[it], it, prv_gcd);
}
return 0;
}
void update_value(int pos, int val)
{
int L_pos = get_left(pos) + 1;
if(a[pos] == 1) L_pos = pos;
t.update(pos, val, 1, n, 0);
sum_t.update(L_pos, pos, pos, 1, n, 0);
a[pos] = val;
int g = a[pos], curr = pos;
while(g != 1 && curr > 0)
{
int j = get_left_equal(curr, g);
int new_r_value = get_right(j + 1);
t.update(pos, a[pos], 1, n, 0);
sum_t.update(j + 1, curr, new_r_value, 1, n, 0);
curr = j;
if(curr > 0) g = gcd(g, a[curr]);
}
}
void update_naive(int pos, int val)
{
a[pos] = val;
t.update(pos, val, 1, n, 0);
for(int i = 1; i <= n; i++)
sum_t.update(i, i, get_right(i), 1, n, 0);
}
int get_r_value(int pos) { return sum_t.query(pos, pos, 1, n, 0).sum; }
int q;
void read()
{
cin >> n >> q;
for(int i = 1; i <= n; i++)
cin >> a[i];
}
int64_t query(int L, int R)
{
int64_t ans = 0;
int low = L, high = R, mid, r = R + 1;
while(low <= high)
{
mid = (low + high) >> 1;
if(get_r_value(mid) > R)
r = mid, high = mid - 1;
else
low = mid + 1;
}
ans -= ((R + 1ll) * 1ll * (R)) / 2ll;
ans += ((L - 1ll) * 1ll * (L)) / 2ll;
ans += (R - r + 1ll) * 1ll * (R + 1ll);
if(L < r) ans += sum_t.query(L, r - 1, 1, n, 0).sum;
return ans;
}
void solve()
{
t.init(1, n, 0);
sum_t.init(1, n, 0);
for(int i = 1; i <= n; i++)
update_value(i, a[i]);
//update_naive(i, a[i]);
while(q--)
{
int type;
cin >> type;
if(type == 1)
{
int pos, val;
cin >> pos >> val;
update_value(pos, val);
//update_naive(pos, val);
}
else
{
int l, r;
cin >> l >> r;
cout << query(l, r) << endl;
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
read();
solve();
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNkZWZpbmUgZW5kbCAnXG4nCiAKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKdGVtcGxhdGU8Y2xhc3MgVCwgY2xhc3MgVDI+IGlubGluZSB2b2lkIGNoa21heChUICZ4LCBjb25zdCBUMiAmeSkgeyBpZih4IDwgeSkgeCA9IHk7IH0KdGVtcGxhdGU8Y2xhc3MgVCwgY2xhc3MgVDI+IGlubGluZSB2b2lkIGNoa21pbihUICZ4LCBjb25zdCBUMiAmeSkgeyBpZih4ID4geSkgeCA9IHk7IH0KY29uc3QgaW50IE1BWE4gPSAoMSA8PCAyMCk7CiAKaW50IGdjZChpbnQgYSwgaW50IGIpIHsgcmV0dXJuIChhID09IDAgfHwgYiA9PSAwKSA/IChhICsgYikgOiAoX19nY2QoYSwgYikpOyB9CiAKc3RydWN0IHNlZ21lbnRfdHJlZQp7CiAgICBzdHJ1Y3Qgbm9kZQogICAgewogICAgICAgIGludDY0X3Qgc3VtLCBsYXp5OwogCiAgICAgICAgbm9kZSgpIHtzdW0gPSAwOyBsYXp5ID0gMDt9CiAgICAgICAgbm9kZShpbnQ2NF90IHZhbCkKICAgICAgICB7CiAgICAgICAgICAgIHN1bSA9IHZhbDsKICAgICAgICAgICAgbGF6eSA9IDA7CiAgICAgICAgfQogICAgfTsKIAogICAgbm9kZSB0ZW1wLCBicm9rZW47CiAKICAgIG5vZGUgbWVyZ2Uobm9kZSBsLCBub2RlIHIpCiAgICB7CiAgICAgICAgdGVtcC5zdW0gPSBsLnN1bSArIHIuc3VtOwogICAgICAgIHRlbXAubGF6eSA9IDA7CiAgICAgICAgcmV0dXJuIHRlbXA7CiAgICB9CiAKICAgIG5vZGUgdHJbNCAqIE1BWE5dOwogCiAgICB2b2lkIHB1c2goaW50IGwsIGludCByLCBpbnQgaWR4KQogICAgewogICAgICAgIGlmKHRyW2lkeF0ubGF6eSkKICAgICAgICB7CiAgICAgICAgICAgIHRyW2lkeF0uc3VtID0gKHIgLSBsICsgMSkgKiB0cltpZHhdLmxhenk7CiAKICAgICAgICAgICAgaWYobCAhPSByKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICB0clsyICogaWR4ICsgMV0ubGF6eSA9IHRyW2lkeF0ubGF6eTsKICAgICAgICAgICAgICAgIHRyWzIgKiBpZHggKyAyXS5sYXp5ID0gdHJbaWR4XS5sYXp5OwogICAgICAgICAgICB9CiAKICAgICAgICAgICAgdHJbaWR4XS5sYXp5ID0gMDsKICAgICAgICB9CiAgICB9CiAKICAgIHZvaWQgaW5pdChpbnQgbCwgaW50IHIsIGludCBpZHgpCiAgICB7CiAgICAgICAgaWYobCA9PSByKQogICAgICAgIHsKICAgICAgICAgICAgdHJbaWR4XSA9IG5vZGUoMCk7CiAgICAgICAgICAgIHJldHVybjsKICAgICAgICB9CiAKICAgICAgICBpbnQgbWlkID0gKGwgKyByKSA+PiAxOwogICAgICAgIGluaXQobCwgbWlkLCAyICogaWR4ICsgMSk7CiAgICAgICAgaW5pdChtaWQgKyAxLCByLCAyICogaWR4ICsgMik7CiAKICAgICAgICB0cltpZHhdID0gbWVyZ2UodHJbMiAqIGlkeCArIDFdLCB0clsyICogaWR4ICsgMl0pOwogICAgfQogCiAgICB2b2lkIHVwZGF0ZShpbnQgcUwsIGludCBxUiwgaW50IHZhbCwgaW50IGwsIGludCByLCBpbnQgaWR4KQogICAgewogICAgICAgIHB1c2gobCwgciwgaWR4KTsKIAogICAgICAgIGlmKHFMID4gciB8fCBsID4gcVIpCiAgICAgICAgICAgIHJldHVybjsKIAogICAgICAgIGlmKHFMIDw9IGwgJiYgciA8PSBxUikKICAgICAgICB7CiAgICAgICAgICAgIHRyW2lkeF0ubGF6eSA9IHZhbDsKICAgICAgICAgICAgcHVzaChsLCByLCBpZHgpOwogICAgICAgICAgICByZXR1cm47CiAgICAgICAgfQogCiAgICAgICAgaW50IG1pZCA9IChsICsgcikgPj4gMTsKICAgICAgICB1cGRhdGUocUwsIHFSLCB2YWwsIGwsIG1pZCwgMiAqIGlkeCArIDEpOwogICAgICAgIHVwZGF0ZShxTCwgcVIsIHZhbCwgbWlkICsgMSwgciwgMiAqIGlkeCArIDIpOwogCiAgICAgICAgdHJbaWR4XSA9IG1lcmdlKHRyWzIgKiBpZHggKyAxXSwgdHJbMiAqIGlkeCArIDJdKTsKICAgIH0KIAogICAgbm9kZSBxdWVyeShpbnQgcUwsIGludCBxUiwgaW50IGwsIGludCByLCBpbnQgaWR4KQogICAgewogICAgICAgIHB1c2gobCwgciwgaWR4KTsKIAogICAgICAgIGlmKGwgPiBxUiB8fCByIDwgcUwpCiAgICAgICAgICAgIHJldHVybiBicm9rZW47CiAKICAgICAgICBpZihxTCA8PSBsICYmIHIgPD0gcVIpCiAgICAgICAgICAgIHJldHVybiB0cltpZHhdOwogCiAgICAgICAgaW50IG1pZCA9IChsICsgcikgPj4gMTsKICAgICAgICByZXR1cm4gbWVyZ2UocXVlcnkocUwsIHFSLCBsLCBtaWQsIDIgKiBpZHggKyAxKSwgcXVlcnkocUwsIHFSLCBtaWQgKyAxLCByLCAyICogaWR4ICsgMikpOwogICAgfQp9OwogCnNlZ21lbnRfdHJlZSBzdW1fdDsKIApzdHJ1Y3Qgbm9kZQp7CiAgICBpbnQgZzsKICAgIG5vZGUoKSB7IGcgPSAwOyB9CiAgICBub2RlKGludCB2YWwpIHsgZyA9IHZhbDsgfQp9OwogCmludCBhW01BWE5dOwpub2RlIHRlbXAsIGJyb2tlbjsKIApub2RlIG1lcmdlKG5vZGUgbCwgbm9kZSByKQp7CiAgICB0ZW1wLmcgPSBnY2QobC5nLCByLmcpOwogICAgcmV0dXJuIHRlbXA7Cn0KIAppbnQgYm91bmRfTFtNQVhOXSwgYm91bmRfUltNQVhOXTsKc3RydWN0IHNlZ21lbnRfdHJlZV9nY2QKewogICAgbm9kZSB0cls0ICogTUFYTl07CiAKICAgIHZvaWQgaW5pdChpbnQgbCwgaW50IHIsIGludCBpZHgpCiAgICB7CiAgICAgICAgYm91bmRfTFtpZHhdID0gbDsKICAgICAgICBib3VuZF9SW2lkeF0gPSByOwogICAgICAgIGlmKGwgPT0gcikKICAgICAgICB7CiAgICAgICAgICAgIHRyW2lkeF0gPSBub2RlKGFbbF0pOwogICAgICAgICAgICByZXR1cm47CiAgICAgICAgfQogCiAgICAgICAgaW50IG1pZCA9IChsICsgcikgPj4gMTsKICAgICAgICBpbml0KGwsIG1pZCwgMiAqIGlkeCArIDEpOwogICAgICAgIGluaXQobWlkICsgMSwgciwgMiAqIGlkeCArIDIpOwogCiAgICAgICAgdHJbaWR4XSA9IG1lcmdlKHRyWzIgKiBpZHggKyAxXSwgdHJbMiAqIGlkeCArIDJdKTsKICAgIH0KIAogICAgdm9pZCB1cGRhdGUoaW50IHBvcywgaW50IHZhbCwgaW50IGwsIGludCByLCBpbnQgaWR4KQogICAgewogICAgICAgIGlmKGwgPiBwb3MgfHwgciA8IHBvcykKICAgICAgICAgICAgcmV0dXJuOwogCiAgICAgICAgaWYobCA9PSByICYmIGwgPT0gcG9zKQogICAgICAgIHsKICAgICAgICAgICAgdHJbaWR4XS5nID0gdmFsOwogICAgICAgICAgICByZXR1cm47CiAgICAgICAgfQogCiAgICAgICAgaW50IG1pZCA9IChsICsgcikgPj4gMTsKICAgICAgICB1cGRhdGUocG9zLCB2YWwsIGwsIG1pZCwgMiAqIGlkeCArIDEpOwogICAgICAgIHVwZGF0ZShwb3MsIHZhbCwgbWlkICsgMSwgciwgMiAqIGlkeCArIDIpOwogCiAgICAgICAgdHJbaWR4XSA9IG1lcmdlKHRyWzIgKiBpZHggKyAxXSwgdHJbMiAqIGlkeCArIDJdKTsKICAgIH0KIAogICAgdm9pZCBnZXRfbm9kZXMoaW50IHFMLCBpbnQgcVIsIGludCBsLCBpbnQgciwgaW50IGlkeCwgdmVjdG9yPGludD4gJmxpKQogICAgewogICAgICAgIGlmKGwgPiBxUiB8fCByIDwgcUwpIHJldHVybjsKICAgICAgICBpZihxTCA8PSBsICYmIHIgPD0gcVIpCiAgICAgICAgewogICAgICAgICAgICBsaS5wdXNoX2JhY2soaWR4KTsKICAgICAgICAgICAgcmV0dXJuOwogICAgICAgIH0KIAogICAgICAgIGludCBtaWQgPSAobCArIHIpID4+IDE7CiAgICAgICAgZ2V0X25vZGVzKHFMLCBxUiwgbCwgbWlkLCAyICogaWR4ICsgMSwgbGkpOwogICAgICAgIGdldF9ub2RlcyhxTCwgcVIsIG1pZCArIDEsIHIsIDIgKiBpZHggKyAyLCBsaSk7CiAgICB9CiAKICAgIGludCBnZXRfbGVmdChpbnQgbCwgaW50IHIsIGludCBpZHgsIGludCBYKQogICAgewogICAgICAgIGlmKGwgPT0gcikgcmV0dXJuIGw7CiAKICAgICAgICBpbnQgbWlkID0gKGwgKyByKSA+PiAxLCBuZXdfZ2NkID0gZ2NkKFgsIHRyWzIgKiBpZHggKyAyXS5nKTsKICAgICAgICBpZihuZXdfZ2NkID09IDEpIHJldHVybiBnZXRfbGVmdChtaWQgKyAxLCByLCAyICogaWR4ICsgMiwgWCk7CiAgICAgICAgZWxzZSByZXR1cm4gZ2V0X2xlZnQobCwgbWlkLCAyICogaWR4ICsgMSwgbmV3X2djZCk7CiAgICB9CiAKICAgIGludCBnZXRfbGVmdF9zYW1lKGludCBsLCBpbnQgciwgaW50IGlkeCwgaW50IFgpCiAgICB7CiAgICAgICAgaWYobCA9PSByKSByZXR1cm4gbDsKIAogICAgICAgIGludCBtaWQgPSAobCArIHIpID4+IDEsIG5ld19nY2QgPSBnY2QoWCwgdHJbMiAqIGlkeCArIDJdLmcpOwogICAgICAgIGlmKG5ld19nY2QgIT0gWCkgcmV0dXJuIGdldF9sZWZ0X3NhbWUobWlkICsgMSwgciwgMiAqIGlkeCArIDIsIFgpOwogICAgICAgIGVsc2UgcmV0dXJuIGdldF9sZWZ0X3NhbWUobCwgbWlkLCAyICogaWR4ICsgMSwgbmV3X2djZCk7CiAgICB9CiAKICAgIGludCBnZXRfcmlnaHQoaW50IGwsIGludCByLCBpbnQgaWR4LCBpbnQgWCkKICAgIHsKICAgICAgICBpZihsID09IHIpIHJldHVybiBsOwogCiAgICAgICAgaW50IG1pZCA9IChsICsgcikgPj4gMSwgbmV3X2djZCA9IGdjZChYLCB0clsyICogaWR4ICsgMV0uZyk7CiAgICAgICAgaWYobmV3X2djZCA9PSAxKSByZXR1cm4gZ2V0X3JpZ2h0KGwsIG1pZCwgMiAqIGlkeCArIDEsIFgpOwogICAgICAgIGVsc2UgcmV0dXJuIGdldF9yaWdodChtaWQgKyAxLCByLCAyICogaWR4ICsgMiwgbmV3X2djZCk7CiAgICB9Cn07CiAKaW50IG47CnNlZ21lbnRfdHJlZV9nY2QgdDsKIAppbnQgZ2V0X2xlZnQoaW50IHBvcykKewogICAgdmVjdG9yPGludD4gbGk7CiAgICB0LmdldF9ub2RlcygxLCBwb3MsIDEsIG4sIDAsIGxpKTsKICAgIHJldmVyc2UobGkuYmVnaW4oKSwgbGkuZW5kKCkpOwogCiAgICBpbnQgY19nY2QgPSAwOwogICAgZm9yKGludCBpdDogbGkpCiAgICB7CiAgICAgICAgaW50IHBydl9nY2QgPSBjX2djZDsKICAgICAgICBjX2djZCA9IGdjZChjX2djZCwgdC50cltpdF0uZyk7CiAgICAgICAgaWYoY19nY2QgPT0gMSkgcmV0dXJuIHQuZ2V0X2xlZnQoYm91bmRfTFtpdF0sIGJvdW5kX1JbaXRdLCBpdCwgcHJ2X2djZCk7CiAgICB9CiAKICAgIHJldHVybiAwOwp9CiAKaW50IGdldF9yaWdodChpbnQgcG9zKQp7CiAgICB2ZWN0b3I8aW50PiBsaTsKICAgIHQuZ2V0X25vZGVzKHBvcywgbiwgMSwgbiwgMCwgbGkpOwogCiAgICBpbnQgY19nY2QgPSAwOwogICAgZm9yKGludCBpdDogbGkpCiAgICB7CiAgICAgICAgaW50IHBydl9nY2QgPSBjX2djZDsKICAgICAgICBjX2djZCA9IGdjZChjX2djZCwgdC50cltpdF0uZyk7CiAgICAgICAgaWYoY19nY2QgPT0gMSkgcmV0dXJuIHQuZ2V0X3JpZ2h0KGJvdW5kX0xbaXRdLCBib3VuZF9SW2l0XSwgaXQsIHBydl9nY2QpOwogICAgfQogCiAgICByZXR1cm4gbiArIDE7Cn0KIAppbnQgZ2V0X2xlZnRfZXF1YWwoaW50IHBvcywgaW50IEcpCnsgICAgCiAgICB2ZWN0b3I8aW50PiBsaTsKICAgIHQuZ2V0X25vZGVzKDEsIHBvcywgMSwgbiwgMCwgbGkpOwogICAgcmV2ZXJzZShsaS5iZWdpbigpLCBsaS5lbmQoKSk7CiAKICAgIGludCBjX2djZCA9IEc7CiAgICBmb3IoaW50IGl0OiBsaSkKICAgIHsKICAgICAgICBpbnQgcHJ2X2djZCA9IGNfZ2NkOwogICAgICAgIGNfZ2NkID0gZ2NkKGNfZ2NkLCB0LnRyW2l0XS5nKTsKICAgICAgICBpZihjX2djZCA8IEcpIHJldHVybiB0LmdldF9sZWZ0X3NhbWUoYm91bmRfTFtpdF0sIGJvdW5kX1JbaXRdLCBpdCwgcHJ2X2djZCk7CiAgICB9CiAKICAgIHJldHVybiAwOwp9CiAKdm9pZCB1cGRhdGVfdmFsdWUoaW50IHBvcywgaW50IHZhbCkKewogICAgaW50IExfcG9zID0gZ2V0X2xlZnQocG9zKSArIDE7CiAgICBpZihhW3Bvc10gPT0gMSkgTF9wb3MgPSBwb3M7CiAgICAKICAgIHQudXBkYXRlKHBvcywgdmFsLCAxLCBuLCAwKTsKICAgIHN1bV90LnVwZGF0ZShMX3BvcywgcG9zLCBwb3MsIDEsIG4sIDApOwogICAgYVtwb3NdID0gdmFsOwogCiAgICBpbnQgZyA9IGFbcG9zXSwgY3VyciA9IHBvczsKICAgIHdoaWxlKGcgIT0gMSAmJiBjdXJyID4gMCkKICAgIHsKICAgICAgICBpbnQgaiA9IGdldF9sZWZ0X2VxdWFsKGN1cnIsIGcpOwogCiAgICAgICAgaW50IG5ld19yX3ZhbHVlID0gZ2V0X3JpZ2h0KGogKyAxKTsKICAgICAgICB0LnVwZGF0ZShwb3MsIGFbcG9zXSwgMSwgbiwgMCk7CiAKICAgICAgICBzdW1fdC51cGRhdGUoaiArIDEsIGN1cnIsIG5ld19yX3ZhbHVlLCAxLCBuLCAwKTsKICAgICAgICBjdXJyID0gajsKIAogICAgICAgIGlmKGN1cnIgPiAwKSBnID0gZ2NkKGcsIGFbY3Vycl0pOwogICAgfQp9CiAKdm9pZCB1cGRhdGVfbmFpdmUoaW50IHBvcywgaW50IHZhbCkKewogICAgYVtwb3NdID0gdmFsOwogICAgdC51cGRhdGUocG9zLCB2YWwsIDEsIG4sIDApOwogICAgZm9yKGludCBpID0gMTsgaSA8PSBuOyBpKyspCiAgICAgICAgc3VtX3QudXBkYXRlKGksIGksIGdldF9yaWdodChpKSwgMSwgbiwgMCk7Cn0KIAppbnQgZ2V0X3JfdmFsdWUoaW50IHBvcykgeyByZXR1cm4gc3VtX3QucXVlcnkocG9zLCBwb3MsIDEsIG4sIDApLnN1bTsgfQogCmludCBxOwogCnZvaWQgcmVhZCgpCnsKICAgIGNpbiA+PiBuID4+IHE7IAogICAgZm9yKGludCBpID0gMTsgaSA8PSBuOyBpKyspCiAgICAgICAgY2luID4+IGFbaV07Cn0KIAppbnQ2NF90IHF1ZXJ5KGludCBMLCBpbnQgUikKewogICAgaW50NjRfdCBhbnMgPSAwOwogCiAgICBpbnQgbG93ID0gTCwgaGlnaCA9IFIsIG1pZCwgciA9IFIgKyAxOwogICAgd2hpbGUobG93IDw9IGhpZ2gpCiAgICB7CiAgICAgICAgbWlkID0gKGxvdyArIGhpZ2gpID4+IDE7CiAgICAgICAgaWYoZ2V0X3JfdmFsdWUobWlkKSA+IFIpCiAgICAgICAgICAgIHIgPSBtaWQsIGhpZ2ggPSBtaWQgLSAxOwogICAgICAgIGVsc2UgCiAgICAgICAgICAgIGxvdyA9IG1pZCArIDE7CiAgICB9CiAKICAgIGFucyAtPSAoKFIgKyAxbGwpICogMWxsICogKFIpKSAvIDJsbDsKICAgIGFucyArPSAoKEwgLSAxbGwpICogMWxsICogKEwpKSAvIDJsbDsKIAogICAgYW5zICs9IChSIC0gciArIDFsbCkgKiAxbGwgKiAoUiArIDFsbCk7CiAgICBpZihMIDwgcikgYW5zICs9IHN1bV90LnF1ZXJ5KEwsIHIgLSAxLCAxLCBuLCAwKS5zdW07CiAKICAgIHJldHVybiBhbnM7Cn0KIAp2b2lkIHNvbHZlKCkKewogICAgdC5pbml0KDEsIG4sIDApOwogICAgc3VtX3QuaW5pdCgxLCBuLCAwKTsgICAgCiAKICAgIGZvcihpbnQgaSA9IDE7IGkgPD0gbjsgaSsrKQogICAgICAgIHVwZGF0ZV92YWx1ZShpLCBhW2ldKTsKICAgICAgICAvL3VwZGF0ZV9uYWl2ZShpLCBhW2ldKTsKIAogICAgd2hpbGUocS0tKQogICAgewogICAgICAgIGludCB0eXBlOwogICAgICAgIGNpbiA+PiB0eXBlOwogCiAgICAgICAgaWYodHlwZSA9PSAxKQogICAgICAgIHsKICAgICAgICAgICAgaW50IHBvcywgdmFsOwogICAgICAgICAgICBjaW4gPj4gcG9zID4+IHZhbDsKICAgICAgICAgICAgdXBkYXRlX3ZhbHVlKHBvcywgdmFsKTsKICAgICAgICAgICAgLy91cGRhdGVfbmFpdmUocG9zLCB2YWwpOwogICAgICAgIH0KICAgICAgICBlbHNlCiAgICAgICAgewogICAgICAgICAgICBpbnQgbCwgcjsKICAgICAgICAgICAgY2luID4+IGwgPj4gcjsKICAgICAgICAgICAgY291dCA8PCBxdWVyeShsLCByKSA8PCBlbmRsOwogICAgICAgIH0KICAgIH0KfQogCmludCBtYWluKCkKewogICAgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CiAgICBjaW4udGllKE5VTEwpOwogCiAgICByZWFkKCk7CiAgICBzb2x2ZSgpOwogICAgcmV0dXJuIDA7Cn0=