#include <bits/stdc++.h>
namespace SegmentTreeLazy {
/*******************************************************************************
* SegmentTree<Value, Extra, Traits> - segment tree class with lazy propagation, 0-indexed
* Default operations: minimal value on segment and addition on segment for int64_t type
* Use Traits<Value,Extra> for definition of:
* 1) neutral element for `Value`;
* 2) neutral element for `Extra`;
* 3) how should combine `Extra` with `Value`;
* 4) how should combine `Value` with `Value` (children to root);
* 5) how should combine `Extra` with `Extra`;
* See examples below: TraitsMinAdd<Value, Extra>
******************************************************************************/
/*******************************************************************************
* Traits for minimal value on segment.
* Get-query: get minimal value in segment [l, r]
* Update-query: add const to each value in segment [l, r]
******************************************************************************/
template<typename Value, typename Extra>
struct TraitsMinAdd {
// Definition of neutral element for `Value`:
static Value valueNeutral() { return std::numeric_limits<Value>::max(); }
// Definition of neutral element for `Extra`:
static Extra extraNeutral() { return Extra(0); }
// Definition of how should combine `Extra` with `Value`:
template<typename Node>
static Value getValue(const Node& src) {
return src.value() + src.extra();
}
// Definition of how should combine `Value` with `Value` (children to root):
template<typename NodeRoot, typename NodeLt, typename NodeRt>
static void pull(NodeRoot root, const NodeLt& lt, const NodeRt& rt) {
root.value() = std::min(getValue(lt), getValue(rt));
}
// Definition of how should combine `Extra` with `Extra`:
template<typename NodeDst, typename NodeSrc>
static void push(NodeDst dst, const NodeSrc& src) {
dst.extra() += src.extra();
}
};
/*******************************************************************************
* Additional traits, implemented below
******************************************************************************/
template<typename Value, typename Extra> struct TraitsMaxAdd;
/*******************************************************************************
* SegmentTree, see description above
******************************************************************************/
template<typename Value = int64_t, typename Extra = int64_t, typename Traits = TraitsMinAdd<Value, Extra> >
struct SegmentTree {
/*******************************************************************************
* Node class
******************************************************************************/
struct Node {
Value value;
Extra extra;
Node(Value value_ = Traits::valueNeutral(), Extra extra_ = Traits::extraNeutral())
: value(value_), extra(extra_) { }
Value getValue(int l, int r) const { return Traits::getValue(NodeWrapper<Node>(l, r, *this)); }
};
/*******************************************************************************
* NodeWrapper class
******************************************************************************/
template<typename NodeType>
struct NodeWrapper {
int l, r;
NodeType node;
NodeWrapper(int l_, int r_, NodeType node_)
: l(l_), r(r_), node(node_) { }
int left() const { return l; }
int right() const { return r; }
int mid() const { return (l+r)/2; }
int len() const { return r - l + 1; }
Value& value() { return node.value; }
Extra& extra() { return node.extra; }
const Value& value() const { return node.value; }
const Extra& extra() const { return node.extra; }
};
/*******************************************************************************
* SegmentTree public data: n - number of items, data - vector for nodes
******************************************************************************/
int n; std::vector<Node> data;
/*******************************************************************************
* Resize segment tree data to needed size
******************************************************************************/
void resize(int n_) {
n = n_;
int pow = 1;
while (pow < n) { pow *= 2; }
data.assign(2 * pow, Node());
}
/*******************************************************************************
* Lazy propagation from node to its children
******************************************************************************/
void push(int v, int l, int r, int m) {
if (data[v].extra != Traits::extraNeutral()) {
Traits::push(
NodeWrapper<Node&>(l, m, data[2*v+1]),
NodeWrapper<const Node&>(l, r, data[v])
);
Traits::push(
NodeWrapper<Node&>(m+1, r, data[2*v+2]),
NodeWrapper<const Node&>( l, r, data[v])
);
data[v].extra = Traits::extraNeutral();
}
}
/*******************************************************************************
* Update node using children values
******************************************************************************/
void pull(int v, int l, int r, int m) {
assert(data[v].extra == Traits::extraNeutral());
Traits::pull(
NodeWrapper<Node&>( l, r, data[v]),
NodeWrapper<const Node&>( l, m, data[2*v+1]),
NodeWrapper<const Node&>(m+1, r, data[2*v+2])
);
}
/*******************************************************************************
* Build segtree from array with given values
******************************************************************************/
template<typename T>
void build(const std::vector<T>& arr, const int v, const int tl, const int tr) {
if (tl == tr) {
data[v] = Node(arr[tl]);
} else {
const int tm = (tl + tr) / 2;
build(arr, 2*v+1, tl, tm);
build(arr, 2*v+2, tm+1, tr);
pull(v, tl, tr, tm);
}
}
template<typename T>
void build(const std::vector<T>& arr) {
resize((int)arr.size());
build(arr, 0, 0, n-1);
}
/*******************************************************************************
* Get-query on range [ql, qr]
******************************************************************************/
Node get(int ql, int qr, const int v, const int tl, const int tr) {
if (ql == tl && qr == tr) {
return data[v];
} else {
int tm = (tl + tr) / 2;
push(v, tl, tr, tm);
Node ret;
if (qr <= tm) {
ret = get(ql, qr, 2*v+1, tl, tm);
} else if (ql > tm) {
ret = get(ql, qr, 2*v+2, tm+1, tr);
} else {
const auto lt = get( ql, tm, 2*v+1, tl, tm);
const auto rt = get(tm+1, qr, 2*v+2, tm+1, tr);
Traits::pull(
NodeWrapper<Node&>( ql, qr, ret),
NodeWrapper<const Node&>( ql, tm, lt),
NodeWrapper<const Node&>(tm+1, qr, rt)
);
}
pull(v, tl, tr, tm);
return ret;
}
}
Value get(const int ql, const int qr) { return get(ql, qr, 0, 0, n-1).getValue(ql, qr); }
/*******************************************************************************
* Update query on range [ql, qr] by extra
******************************************************************************/
void update(const int ql, const int qr, const Extra& extra, const int v, const int tl, const int tr) {
if (ql == tl && tr == qr) {
Traits::push(
NodeWrapper<Node&>(tl, tr, data[v]),
NodeWrapper<Node>(ql, qr, Node(Traits::valueNeutral(), extra))
);
} else {
int tm = (tl + tr) / 2;
push(v, tl, tr, tm);
if (qr <= tm) {
update(ql, qr, extra, 2*v+1, tl, tm);
} else if (ql > tm) {
update(ql, qr, extra, 2*v+2,tm+1,tr);
} else {
update(ql, tm, extra, 2*v+1, tl, tm);
update(tm+1, qr, extra, 2*v+2, tm+1, tr);
}
pull(v, tl, tr, tm);
}
}
void update(const int ql, const int qr, const Extra& extra) {
update(ql, qr, extra, 0, 0, n-1);
}
};
/*******************************************************************************
* Traits for maximal value on segment.
* Get-query: get maximal value in segment [l, r]
* Update-query: add const to each value in segment [l, r]
******************************************************************************/
template<typename Value, typename Extra>
struct TraitsMaxAdd {
// Definition of neutral element for `Value`:
static Value valueNeutral() { return std::numeric_limits<Value>::min(); }
// Definition of neutral element for `Extra`:
static Extra extraNeutral() { return Extra(0); }
// Definition of how should combine `Extra` with `Value`:
template<typename Node>
static Value getValue(const Node& src) {
return src.value() + src.extra();
}
// Definition of how should combine `Value` with `Value` (children to root):
template<typename NodeRoot, typename NodeLt, typename NodeRt>
static void pull(NodeRoot root, const NodeLt& lt, const NodeRt& rt) {
root.value() = std::max(getValue(lt), getValue(rt));
}
// Definition of how should combine `Extra` with `Extra`:
template<typename NodeDst, typename NodeSrc>
static void push(NodeDst dst, const NodeSrc& src) {
dst.extra() += src.extra();
}
};
}
int main() {
// Creating queries 1) arr[l..r] += x and 2) max(arr[l..r])
const int n = (int)1e6;
const int q = (int)1e6;
std::mt19937 gen;
std::uniform_int_distribution<int> dist(0,n-1);
std::vector<int> arr(n);
for (auto &it : arr) { it = dist(gen); }
std::vector<int> queryType(q), queryLeft(q), queryRight(q), queryExtra(q);
for (int i = 0; i < q; ++i) {
queryType[i] = 1 + dist(gen) % 2;
queryLeft[i] = dist(gen);
queryRight[i] = dist(gen);
if (queryLeft[i] > queryRight[i]) { std::swap(queryLeft[i], queryRight[i]); }
queryExtra[i] = dist(gen) - n / 2;
}
// Create SegmentTree
SegmentTreeLazy::SegmentTree<int64_t, int64_t, SegmentTreeLazy::TraitsMaxAdd<int64_t,int64_t>> segtree;
segtree.build(arr);
int64_t checkValue = 0;
for (int i = 0; i < q; ++i) {
if (queryType[i] == 1) {
segtree.update(queryLeft[i], queryRight[i], queryExtra[i]);
} else {
checkValue += segtree.get(queryLeft[i], queryRight[i]);
}
}
std::cout << "checkValue = " << checkValue << std::endl;
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CgpuYW1lc3BhY2UgU2VnbWVudFRyZWVMYXp5IHsKICAgIAogICAgLyoqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioKICAgICAqICBTZWdtZW50VHJlZTxWYWx1ZSwgRXh0cmEsIFRyYWl0cz4gLSBzZWdtZW50IHRyZWUgY2xhc3Mgd2l0aCBsYXp5IHByb3BhZ2F0aW9uLCAwLWluZGV4ZWQKICAgICAqICBEZWZhdWx0IG9wZXJhdGlvbnM6IG1pbmltYWwgdmFsdWUgb24gc2VnbWVudCBhbmQgYWRkaXRpb24gb24gc2VnbWVudCBmb3IgaW50NjRfdCB0eXBlCiAgICAgKiAgVXNlIFRyYWl0czxWYWx1ZSxFeHRyYT4gZm9yIGRlZmluaXRpb24gb2Y6CiAgICAgKiAgICAgIDEpICBuZXV0cmFsIGVsZW1lbnQgZm9yIGBWYWx1ZWA7CiAgICAgKiAgICAgIDIpICBuZXV0cmFsIGVsZW1lbnQgZm9yIGBFeHRyYWA7CiAgICAgKiAgICAgIDMpICBob3cgc2hvdWxkIGNvbWJpbmUgYEV4dHJhYCB3aXRoIGBWYWx1ZWA7CiAgICAgKiAgICAgIDQpICBob3cgc2hvdWxkIGNvbWJpbmUgYFZhbHVlYCB3aXRoIGBWYWx1ZWAgKGNoaWxkcmVuIHRvIHJvb3QpOwogICAgICogICAgICA1KSAgaG93IHNob3VsZCBjb21iaW5lIGBFeHRyYWAgd2l0aCBgRXh0cmFgOwogICAgICogIFNlZSBleGFtcGxlcyBiZWxvdzogVHJhaXRzTWluQWRkPFZhbHVlLCBFeHRyYT4KICAgICAqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKiovCiAgICAKICAgIC8qKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqCiAgICAgKiAgVHJhaXRzIGZvciBtaW5pbWFsIHZhbHVlIG9uIHNlZ21lbnQuIAogICAgICogIEdldC1xdWVyeTogICAgZ2V0IG1pbmltYWwgdmFsdWUgaW4gc2VnbWVudCBbbCwgcl0KICAgICAqICBVcGRhdGUtcXVlcnk6IGFkZCBjb25zdCB0byBlYWNoIHZhbHVlIGluIHNlZ21lbnQgW2wsIHJdCiAgICAgKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqLwogICAgdGVtcGxhdGU8dHlwZW5hbWUgVmFsdWUsIHR5cGVuYW1lIEV4dHJhPgogICAgc3RydWN0IFRyYWl0c01pbkFkZCB7CiAgICAgICAgLy8gRGVmaW5pdGlvbiBvZiBuZXV0cmFsIGVsZW1lbnQgZm9yIGBWYWx1ZWA6CiAgICAgICAgc3RhdGljIFZhbHVlIHZhbHVlTmV1dHJhbCgpIHsgcmV0dXJuIHN0ZDo6bnVtZXJpY19saW1pdHM8VmFsdWU+OjptYXgoKTsgfQogICAgICAgIC8vIERlZmluaXRpb24gb2YgbmV1dHJhbCBlbGVtZW50IGZvciBgRXh0cmFgOgogICAgICAgIHN0YXRpYyBFeHRyYSBleHRyYU5ldXRyYWwoKSB7IHJldHVybiBFeHRyYSgwKTsgfQogICAgICAgIC8vIERlZmluaXRpb24gb2YgaG93IHNob3VsZCBjb21iaW5lIGBFeHRyYWAgd2l0aCBgVmFsdWVgOgogICAgICAgIHRlbXBsYXRlPHR5cGVuYW1lIE5vZGU+CiAgICAgICAgc3RhdGljIFZhbHVlIGdldFZhbHVlKGNvbnN0IE5vZGUmIHNyYykgewogICAgICAgICAgICByZXR1cm4gc3JjLnZhbHVlKCkgKyBzcmMuZXh0cmEoKTsKICAgICAgICB9CiAgICAgICAgLy8gRGVmaW5pdGlvbiBvZiBob3cgc2hvdWxkIGNvbWJpbmUgYFZhbHVlYCB3aXRoIGBWYWx1ZWAgKGNoaWxkcmVuIHRvIHJvb3QpOgogICAgICAgIHRlbXBsYXRlPHR5cGVuYW1lIE5vZGVSb290LCB0eXBlbmFtZSBOb2RlTHQsIHR5cGVuYW1lIE5vZGVSdD4KICAgICAgICBzdGF0aWMgdm9pZCBwdWxsKE5vZGVSb290IHJvb3QsIGNvbnN0IE5vZGVMdCYgbHQsIGNvbnN0IE5vZGVSdCYgcnQpIHsKICAgICAgICAgICAgcm9vdC52YWx1ZSgpID0gc3RkOjptaW4oZ2V0VmFsdWUobHQpLCBnZXRWYWx1ZShydCkpOwogICAgICAgIH0KICAgICAgICAvLyBEZWZpbml0aW9uIG9mIGhvdyBzaG91bGQgY29tYmluZSBgRXh0cmFgIHdpdGggYEV4dHJhYDoKICAgICAgICB0ZW1wbGF0ZTx0eXBlbmFtZSBOb2RlRHN0LCB0eXBlbmFtZSBOb2RlU3JjPgogICAgICAgIHN0YXRpYyB2b2lkIHB1c2goTm9kZURzdCBkc3QsIGNvbnN0IE5vZGVTcmMmIHNyYykgewogICAgICAgICAgICBkc3QuZXh0cmEoKSArPSBzcmMuZXh0cmEoKTsKICAgICAgICB9CiAgICB9OwogICAgCiAgICAvKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKgogICAgICogIEFkZGl0aW9uYWwgdHJhaXRzLCBpbXBsZW1lbnRlZCBiZWxvdyAKICAgICAqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKiovCiAgICB0ZW1wbGF0ZTx0eXBlbmFtZSBWYWx1ZSwgdHlwZW5hbWUgRXh0cmE+ICBzdHJ1Y3QgVHJhaXRzTWF4QWRkOwogICAgCiAgICAvKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKgogICAgICogIFNlZ21lbnRUcmVlLCBzZWUgZGVzY3JpcHRpb24gYWJvdmUKICAgICAqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKiovCiAgICB0ZW1wbGF0ZTx0eXBlbmFtZSBWYWx1ZSA9IGludDY0X3QsIHR5cGVuYW1lIEV4dHJhID0gaW50NjRfdCwgdHlwZW5hbWUgVHJhaXRzID0gVHJhaXRzTWluQWRkPFZhbHVlLCBFeHRyYT4gPgogICAgc3RydWN0IFNlZ21lbnRUcmVlIHsKICAgICAgICAKICAgICAgICAvKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKgogICAgICAgICAqICBOb2RlIGNsYXNzCiAgICAgICAgICoqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKi8KICAgICAgICBzdHJ1Y3QgTm9kZSB7CiAgICAgICAgICAgIFZhbHVlIHZhbHVlOwogICAgICAgICAgICAKICAgICAgICAgICAgRXh0cmEgZXh0cmE7CiAgICAgICAgICAgIAogICAgICAgICAgICBOb2RlKFZhbHVlIHZhbHVlXyA9IFRyYWl0czo6dmFsdWVOZXV0cmFsKCksIEV4dHJhIGV4dHJhXyA9IFRyYWl0czo6ZXh0cmFOZXV0cmFsKCkpCiAgICAgICAgICAgICAgICA6IHZhbHVlKHZhbHVlXyksIGV4dHJhKGV4dHJhXykgeyB9CiAgICAgICAgICAgIAogICAgICAgICAgICBWYWx1ZSBnZXRWYWx1ZShpbnQgbCwgaW50IHIpIGNvbnN0IHsgcmV0dXJuIFRyYWl0czo6Z2V0VmFsdWUoTm9kZVdyYXBwZXI8Tm9kZT4obCwgciwgKnRoaXMpKTsgfQogICAgICAgIH07CiAgICAgICAgCiAgICAgICAgLyoqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioKICAgICAgICAgKiAgTm9kZVdyYXBwZXIgY2xhc3MKICAgICAgICAgKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqLwogICAgICAgIHRlbXBsYXRlPHR5cGVuYW1lIE5vZGVUeXBlPgogICAgICAgIHN0cnVjdCBOb2RlV3JhcHBlciB7CiAgICAgICAgICAgIGludCBsLCByOwogICAgICAgICAgICBOb2RlVHlwZSBub2RlOwogICAgICAgICAgICBOb2RlV3JhcHBlcihpbnQgbF8sIGludCByXywgTm9kZVR5cGUgbm9kZV8pCiAgICAgICAgICAgICAgICA6IGwobF8pLCByKHJfKSwgbm9kZShub2RlXykgeyB9CiAgICAgICAgICAgIGludCAgbGVmdCgpIGNvbnN0IHsgcmV0dXJuIGw7IH0KICAgICAgICAgICAgaW50IHJpZ2h0KCkgY29uc3QgeyByZXR1cm4gcjsgfQogICAgICAgICAgICBpbnQgICBtaWQoKSBjb25zdCB7IHJldHVybiAobCtyKS8yOyB9CiAgICAgICAgICAgIGludCAgIGxlbigpIGNvbnN0IHsgcmV0dXJuIHIgLSBsICsgMTsgfQogICAgICAgICAgICBWYWx1ZSYgdmFsdWUoKSB7IHJldHVybiBub2RlLnZhbHVlOyB9CiAgICAgICAgICAgIEV4dHJhJiBleHRyYSgpIHsgcmV0dXJuIG5vZGUuZXh0cmE7IH0KICAgICAgICAgICAgY29uc3QgVmFsdWUmIHZhbHVlKCkgY29uc3QgeyByZXR1cm4gbm9kZS52YWx1ZTsgfQogICAgICAgICAgICBjb25zdCBFeHRyYSYgZXh0cmEoKSBjb25zdCB7IHJldHVybiBub2RlLmV4dHJhOyB9CiAgICAgICAgfTsKICAgICAgICAKICAgICAgICAvKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKgogICAgICAgICAqICBTZWdtZW50VHJlZSBwdWJsaWMgZGF0YTogbiAtIG51bWJlciBvZiBpdGVtcywgZGF0YSAtIHZlY3RvciBmb3Igbm9kZXMKICAgICAgICAgKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqLwogICAgICAgIGludCBuOyBzdGQ6OnZlY3RvcjxOb2RlPiBkYXRhOwogICAgICAgIAogICAgICAgIAogICAgICAgIC8qKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqCiAgICAgICAgICogIFJlc2l6ZSBzZWdtZW50IHRyZWUgZGF0YSB0byBuZWVkZWQgc2l6ZQogICAgICAgICAqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKiovCiAgICAgICAgdm9pZCByZXNpemUoaW50IG5fKSB7CiAgICAgICAgICAgIG4gPSBuXzsKICAgICAgICAgICAgaW50IHBvdyA9IDE7CiAgICAgICAgICAgIHdoaWxlIChwb3cgPCBuKSB7IHBvdyAqPSAyOyB9CiAgICAgICAgICAgIGRhdGEuYXNzaWduKDIgKiBwb3csIE5vZGUoKSk7CiAgICAgICAgfQogICAgICAgIAogICAgICAgIC8qKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqCiAgICAgICAgICogIExhenkgcHJvcGFnYXRpb24gZnJvbSBub2RlIHRvIGl0cyBjaGlsZHJlbgogICAgICAgICAqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKiovCiAgICAgICAgdm9pZCBwdXNoKGludCB2LCBpbnQgbCwgaW50IHIsIGludCBtKSB7CiAgICAgICAgICAgIGlmIChkYXRhW3ZdLmV4dHJhICE9IFRyYWl0czo6ZXh0cmFOZXV0cmFsKCkpIHsKICAgICAgICAgICAgICAgIFRyYWl0czo6cHVzaCgKICAgICAgICAgICAgICAgICAgICBOb2RlV3JhcHBlcjxOb2RlJj4obCwgbSwgZGF0YVsyKnYrMV0pLCAKICAgICAgICAgICAgICAgICAgICBOb2RlV3JhcHBlcjxjb25zdCBOb2RlJj4obCwgciwgZGF0YVt2XSkKICAgICAgICAgICAgICAgICk7CiAgICAgICAgICAgICAgICBUcmFpdHM6OnB1c2goCiAgICAgICAgICAgICAgICAgICAgTm9kZVdyYXBwZXI8Tm9kZSY+KG0rMSwgciwgZGF0YVsyKnYrMl0pLCAKICAgICAgICAgICAgICAgICAgICBOb2RlV3JhcHBlcjxjb25zdCBOb2RlJj4oICBsLCByLCBkYXRhW3ZdKQogICAgICAgICAgICAgICAgKTsKICAgICAgICAgICAgICAgIGRhdGFbdl0uZXh0cmEgPSBUcmFpdHM6OmV4dHJhTmV1dHJhbCgpOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIAogICAgICAgIC8qKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqCiAgICAgICAgICogIFVwZGF0ZSBub2RlIHVzaW5nIGNoaWxkcmVuIHZhbHVlcwogICAgICAgICAqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKiovCiAgICAgICAgdm9pZCBwdWxsKGludCB2LCBpbnQgbCwgaW50IHIsIGludCBtKSB7CiAgICAgICAgICAgIGFzc2VydChkYXRhW3ZdLmV4dHJhID09IFRyYWl0czo6ZXh0cmFOZXV0cmFsKCkpOwogICAgICAgICAgICBUcmFpdHM6OnB1bGwoCiAgICAgICAgICAgICAgICBOb2RlV3JhcHBlcjxOb2RlJj4oICBsLCByLCBkYXRhW3ZdKSwgCiAgICAgICAgICAgICAgICBOb2RlV3JhcHBlcjxjb25zdCBOb2RlJj4oICBsLCBtLCBkYXRhWzIqdisxXSksIAogICAgICAgICAgICAgICAgTm9kZVdyYXBwZXI8Y29uc3QgTm9kZSY+KG0rMSwgciwgZGF0YVsyKnYrMl0pCiAgICAgICAgICAgICk7CiAgICAgICAgfQogICAgICAgIAogICAgICAgIC8qKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqCiAgICAgICAgICogIEJ1aWxkIHNlZ3RyZWUgZnJvbSBhcnJheSB3aXRoIGdpdmVuIHZhbHVlcwogICAgICAgICAqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKiovCiAgICAgICAgdGVtcGxhdGU8dHlwZW5hbWUgVD4KICAgICAgICB2b2lkIGJ1aWxkKGNvbnN0IHN0ZDo6dmVjdG9yPFQ+JiBhcnIsIGNvbnN0IGludCB2LCBjb25zdCBpbnQgdGwsIGNvbnN0IGludCB0cikgewogICAgICAgICAgICBpZiAodGwgPT0gdHIpIHsKICAgICAgICAgICAgICAgIGRhdGFbdl0gPSBOb2RlKGFyclt0bF0pOwogICAgICAgICAgICB9IGVsc2UgewogICAgICAgICAgICAgICAgY29uc3QgaW50IHRtID0gKHRsICsgdHIpIC8gMjsKICAgICAgICAgICAgICAgIGJ1aWxkKGFyciwgMip2KzEsICAgdGwsIHRtKTsKICAgICAgICAgICAgICAgIGJ1aWxkKGFyciwgMip2KzIsIHRtKzEsIHRyKTsKICAgICAgICAgICAgICAgIHB1bGwodiwgdGwsIHRyLCB0bSk7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgCiAgICAgICAgdGVtcGxhdGU8dHlwZW5hbWUgVD4KICAgICAgICB2b2lkIGJ1aWxkKGNvbnN0IHN0ZDo6dmVjdG9yPFQ+JiBhcnIpIHsgCiAgICAgICAgICAgIHJlc2l6ZSgoaW50KWFyci5zaXplKCkpOwogICAgICAgICAgICBidWlsZChhcnIsIDAsIDAsIG4tMSk7CiAgICAgICAgfQoKICAgICAgICAvKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKgogICAgICAgICAqICBHZXQtcXVlcnkgb24gcmFuZ2UgW3FsLCBxcl0KICAgICAgICAgKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqLwogICAgICAgIE5vZGUgZ2V0KGludCBxbCwgaW50IHFyLCBjb25zdCBpbnQgdiwgY29uc3QgaW50IHRsLCBjb25zdCBpbnQgdHIpIHsKICAgICAgICAgICAgaWYgKHFsID09IHRsICYmIHFyID09IHRyKSB7CiAgICAgICAgICAgICAgICByZXR1cm4gZGF0YVt2XTsKICAgICAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgICAgIGludCB0bSA9ICh0bCArIHRyKSAvIDI7CiAgICAgICAgICAgICAgICBwdXNoKHYsIHRsLCB0ciwgdG0pOwogICAgICAgICAgICAgICAgTm9kZSByZXQ7CiAgICAgICAgICAgICAgICBpZiAocXIgPD0gdG0pIHsKICAgICAgICAgICAgICAgICAgICByZXQgPSBnZXQocWwsIHFyLCAyKnYrMSwgICB0bCwgdG0pOwogICAgICAgICAgICAgICAgfSBlbHNlIGlmIChxbCA+IHRtKSB7CiAgICAgICAgICAgICAgICAgICAgcmV0ID0gZ2V0KHFsLCBxciwgMip2KzIsIHRtKzEsIHRyKTsKICAgICAgICAgICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgICAgICAgICAgY29uc3QgYXV0byBsdCA9IGdldCggIHFsLCB0bSwgMip2KzEsICAgdGwsIHRtKTsKICAgICAgICAgICAgICAgICAgICBjb25zdCBhdXRvIHJ0ID0gZ2V0KHRtKzEsIHFyLCAyKnYrMiwgdG0rMSwgdHIpOwogICAgICAgICAgICAgICAgICAgIFRyYWl0czo6cHVsbCgKICAgICAgICAgICAgICAgICAgICAgICAgTm9kZVdyYXBwZXI8Tm9kZSY+KCAgcWwsIHFyLCByZXQpLCAKICAgICAgICAgICAgICAgICAgICAgICAgTm9kZVdyYXBwZXI8Y29uc3QgTm9kZSY+KCAgcWwsIHRtLCBsdCksIAogICAgICAgICAgICAgICAgICAgICAgICBOb2RlV3JhcHBlcjxjb25zdCBOb2RlJj4odG0rMSwgcXIsIHJ0KQogICAgICAgICAgICAgICAgICAgICk7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBwdWxsKHYsIHRsLCB0ciwgdG0pOwogICAgICAgICAgICAgICAgcmV0dXJuIHJldDsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICAKICAgICAgICBWYWx1ZSBnZXQoY29uc3QgaW50IHFsLCBjb25zdCBpbnQgcXIpIHsgcmV0dXJuIGdldChxbCwgcXIsIDAsIDAsIG4tMSkuZ2V0VmFsdWUocWwsIHFyKTsgfQogICAgICAgIAogICAgICAgIC8qKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqCiAgICAgICAgICogIFVwZGF0ZSBxdWVyeSBvbiByYW5nZSBbcWwsIHFyXSBieSBleHRyYQogICAgICAgICAqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKiovCiAgICAgICAgdm9pZCB1cGRhdGUoY29uc3QgaW50IHFsLCBjb25zdCBpbnQgcXIsIGNvbnN0IEV4dHJhJiBleHRyYSwgY29uc3QgaW50IHYsIGNvbnN0IGludCB0bCwgY29uc3QgaW50IHRyKSB7CiAgICAgICAgICAgIGlmIChxbCA9PSB0bCAmJiB0ciA9PSBxcikgewogICAgICAgICAgICAgICAgVHJhaXRzOjpwdXNoKAogICAgICAgICAgICAgICAgICAgIE5vZGVXcmFwcGVyPE5vZGUmPih0bCwgdHIsIGRhdGFbdl0pLAogICAgICAgICAgICAgICAgICAgIE5vZGVXcmFwcGVyPE5vZGU+KHFsLCBxciwgTm9kZShUcmFpdHM6OnZhbHVlTmV1dHJhbCgpLCBleHRyYSkpCiAgICAgICAgICAgICAgICApOwogICAgICAgICAgICB9IGVsc2UgewogICAgICAgICAgICAgICAgaW50IHRtID0gKHRsICsgdHIpIC8gMjsKICAgICAgICAgICAgICAgIHB1c2godiwgdGwsIHRyLCB0bSk7CiAgICAgICAgICAgICAgICBpZiAocXIgPD0gdG0pIHsKICAgICAgICAgICAgICAgICAgICB1cGRhdGUocWwsIHFyLCBleHRyYSwgMip2KzEsIHRsLCB0bSk7CiAgICAgICAgICAgICAgICB9IGVsc2UgaWYgKHFsID4gdG0pIHsKICAgICAgICAgICAgICAgICAgICB1cGRhdGUocWwsIHFyLCBleHRyYSwgMip2KzIsdG0rMSx0cik7CiAgICAgICAgICAgICAgICB9IGVsc2UgewogICAgICAgICAgICAgICAgICAgIHVwZGF0ZShxbCwgdG0sIGV4dHJhLCAyKnYrMSwgICB0bCwgdG0pOwogICAgICAgICAgICAgICAgICAgIHVwZGF0ZSh0bSsxLCBxciwgZXh0cmEsIDIqdisyLCB0bSsxLCB0cik7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBwdWxsKHYsIHRsLCB0ciwgdG0pOwogICAgICAgICAgICB9CiAgICAgICAgfQoKICAgICAgICB2b2lkIHVwZGF0ZShjb25zdCBpbnQgcWwsIGNvbnN0IGludCBxciwgY29uc3QgRXh0cmEmIGV4dHJhKSB7CiAgICAgICAgICAgIHVwZGF0ZShxbCwgcXIsIGV4dHJhLCAwLCAwLCBuLTEpOyAKICAgICAgICB9CgogICAgfTsKICAgIAogICAgLyoqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioKICAgICAqICBUcmFpdHMgZm9yIG1heGltYWwgdmFsdWUgb24gc2VnbWVudC4gCiAgICAgKiAgR2V0LXF1ZXJ5OiAgICBnZXQgbWF4aW1hbCB2YWx1ZSBpbiBzZWdtZW50IFtsLCByXQogICAgICogIFVwZGF0ZS1xdWVyeTogYWRkIGNvbnN0IHRvIGVhY2ggdmFsdWUgaW4gc2VnbWVudCBbbCwgcl0KICAgICAqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKiovCiAgICB0ZW1wbGF0ZTx0eXBlbmFtZSBWYWx1ZSwgdHlwZW5hbWUgRXh0cmE+CiAgICBzdHJ1Y3QgVHJhaXRzTWF4QWRkIHsKICAgICAgICAvLyBEZWZpbml0aW9uIG9mIG5ldXRyYWwgZWxlbWVudCBmb3IgYFZhbHVlYDoKICAgICAgICBzdGF0aWMgVmFsdWUgdmFsdWVOZXV0cmFsKCkgeyByZXR1cm4gc3RkOjpudW1lcmljX2xpbWl0czxWYWx1ZT46Om1pbigpOyB9CiAgICAgICAgLy8gRGVmaW5pdGlvbiBvZiBuZXV0cmFsIGVsZW1lbnQgZm9yIGBFeHRyYWA6CiAgICAgICAgc3RhdGljIEV4dHJhIGV4dHJhTmV1dHJhbCgpIHsgcmV0dXJuIEV4dHJhKDApOyB9CiAgICAgICAgLy8gRGVmaW5pdGlvbiBvZiBob3cgc2hvdWxkIGNvbWJpbmUgYEV4dHJhYCB3aXRoIGBWYWx1ZWA6CiAgICAgICAgdGVtcGxhdGU8dHlwZW5hbWUgTm9kZT4KICAgICAgICBzdGF0aWMgVmFsdWUgZ2V0VmFsdWUoY29uc3QgTm9kZSYgc3JjKSB7CiAgICAgICAgICAgIHJldHVybiBzcmMudmFsdWUoKSArIHNyYy5leHRyYSgpOwogICAgICAgIH0KICAgICAgICAvLyBEZWZpbml0aW9uIG9mIGhvdyBzaG91bGQgY29tYmluZSBgVmFsdWVgIHdpdGggYFZhbHVlYCAoY2hpbGRyZW4gdG8gcm9vdCk6CiAgICAgICAgdGVtcGxhdGU8dHlwZW5hbWUgTm9kZVJvb3QsIHR5cGVuYW1lIE5vZGVMdCwgdHlwZW5hbWUgTm9kZVJ0PgogICAgICAgIHN0YXRpYyB2b2lkIHB1bGwoTm9kZVJvb3Qgcm9vdCwgY29uc3QgTm9kZUx0JiBsdCwgY29uc3QgTm9kZVJ0JiBydCkgewogICAgICAgICAgICByb290LnZhbHVlKCkgPSBzdGQ6Om1heChnZXRWYWx1ZShsdCksIGdldFZhbHVlKHJ0KSk7CiAgICAgICAgfQogICAgICAgIC8vIERlZmluaXRpb24gb2YgaG93IHNob3VsZCBjb21iaW5lIGBFeHRyYWAgd2l0aCBgRXh0cmFgOgogICAgICAgIHRlbXBsYXRlPHR5cGVuYW1lIE5vZGVEc3QsIHR5cGVuYW1lIE5vZGVTcmM+CiAgICAgICAgc3RhdGljIHZvaWQgcHVzaChOb2RlRHN0IGRzdCwgY29uc3QgTm9kZVNyYyYgc3JjKSB7CiAgICAgICAgICAgIGRzdC5leHRyYSgpICs9IHNyYy5leHRyYSgpOwogICAgICAgIH0KICAgIH07ICAgCn0KCmludCBtYWluKCkgewogICAgLy8gQ3JlYXRpbmcgcXVlcmllcyAxKSBhcnJbbC4ucl0gKz0geCBhbmQgMikgbWF4KGFycltsLi5yXSkKICAgIGNvbnN0IGludCBuID0gKGludCkxZTY7CiAgICBjb25zdCBpbnQgcSA9IChpbnQpMWU2OwogICAgc3RkOjptdDE5OTM3IGdlbjsKICAgIHN0ZDo6dW5pZm9ybV9pbnRfZGlzdHJpYnV0aW9uPGludD4gZGlzdCgwLG4tMSk7CiAgICBzdGQ6OnZlY3RvcjxpbnQ+IGFycihuKTsKICAgIGZvciAoYXV0byAmaXQgOiBhcnIpIHsgaXQgPSBkaXN0KGdlbik7IH0KICAgIHN0ZDo6dmVjdG9yPGludD4gcXVlcnlUeXBlKHEpLCBxdWVyeUxlZnQocSksIHF1ZXJ5UmlnaHQocSksIHF1ZXJ5RXh0cmEocSk7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IHE7ICsraSkgewogICAgICAgIHF1ZXJ5VHlwZVtpXSA9IDEgKyBkaXN0KGdlbikgJSAyOwogICAgICAgIHF1ZXJ5TGVmdFtpXSA9IGRpc3QoZ2VuKTsKICAgICAgICBxdWVyeVJpZ2h0W2ldID0gZGlzdChnZW4pOwogICAgICAgIGlmIChxdWVyeUxlZnRbaV0gPiBxdWVyeVJpZ2h0W2ldKSB7IHN0ZDo6c3dhcChxdWVyeUxlZnRbaV0sIHF1ZXJ5UmlnaHRbaV0pOyB9CiAgICAgICAgcXVlcnlFeHRyYVtpXSA9IGRpc3QoZ2VuKSAtIG4gLyAyOwogICAgfQogICAgLy8gQ3JlYXRlIFNlZ21lbnRUcmVlCiAgICBTZWdtZW50VHJlZUxhenk6OlNlZ21lbnRUcmVlPGludDY0X3QsIGludDY0X3QsIFNlZ21lbnRUcmVlTGF6eTo6VHJhaXRzTWF4QWRkPGludDY0X3QsaW50NjRfdD4+IHNlZ3RyZWU7CiAgICBzZWd0cmVlLmJ1aWxkKGFycik7CiAgICBpbnQ2NF90IGNoZWNrVmFsdWUgPSAwOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBxOyArK2kpIHsKICAgICAgICBpZiAocXVlcnlUeXBlW2ldID09IDEpIHsKICAgICAgICAgICAgc2VndHJlZS51cGRhdGUocXVlcnlMZWZ0W2ldLCBxdWVyeVJpZ2h0W2ldLCBxdWVyeUV4dHJhW2ldKTsKICAgICAgICB9IGVsc2UgewogICAgICAgICAgICBjaGVja1ZhbHVlICs9IHNlZ3RyZWUuZ2V0KHF1ZXJ5TGVmdFtpXSwgcXVlcnlSaWdodFtpXSk7CiAgICAgICAgfQogICAgfQogICAgc3RkOjpjb3V0IDw8ICJjaGVja1ZhbHVlID0gIiA8PCBjaGVja1ZhbHVlIDw8IHN0ZDo6ZW5kbDsKICAgIHJldHVybiAwOwp9