#include <iostream>
using namespace std;
template <class TYPE, class MODIFICATION_TYPE> class segments_tree
{
TYPE *SegmentTree;
MODIFICATION_TYPE* ModifierList;
size_t base_capacity;
TYPE (*g)(const TYPE&, const TYPE&);
TYPE (*m)(const TYPE&, const size_t&, const size_t&, const MODIFICATION_TYPE&);
MODIFICATION_TYPE (*combine_modifications)(const MODIFICATION_TYPE&, const MODIFICATION_TYPE&);
TYPE neutral;
MODIFICATION_TYPE neutral_modifier;
/*
TYPE:
Type of elements in the tree.
MODIFICATION_TYPE:
Special type, which allows to synchronize modifications on segment.
SegmentTree: (pointer)
Array-based tree of elements.
base_capacity: (unsigned integer value)
Parental array size, rounded to the closest upper power of 2.
g: (pointer)
Pointer to the funtion (associative binary operation), applied on the given array of elements.
WARNING: The given function must be associative. The monoidal structure of the tree will be ruined otherwise.
m: (pointer)
Pointer to the function, used to modify segments of the tree.
combine_modifications: (pointer)
Pointer to the function, which combines old and new modifications to synchronize them.
neutral: (array element)
The value of element, which is neutral relatively to "g" function.
neutral_modifier:
Marker of non-modified vertexes.
################################
#### INNER HELPER FUNCTIONS ####
################################
try_push: pushes the modifier value from vertex to its left and right leaf.
*/
void try_push(size_t& v, size_t& tl, size_t& tr)
{
if (v < base_capacity) if (ModifierList[v] != neutral_modifier)
{
size_t mid = (tr+tl)/2, i = 2*v;
SegmentTree[i] = m(SegmentTree[i], tl, mid, ModifierList[v]);
SegmentTree[i+1] = m(SegmentTree[i+1], ++mid, tr, ModifierList[v]);
if (i+1 < base_capacity)
{
ModifierList[i] = combine_modifications(ModifierList[i], ModifierList[v]);
ModifierList[i+1] = combine_modifications(ModifierList[i+1], ModifierList[v]);
}
ModifierList[v] = neutral_modifier;
}
}
/*
assign_in:
assigns a new values to the vertexes of the tree,
which are responsible for the value of [l; r] segment.
*/
void assign_in
(
size_t v,
size_t tl, size_t tr,
size_t l, size_t r,
const MODIFICATION_TYPE& new_modification
)
{
if (l <= r)
{
try_push(v, tl, tr);
if (l == tl && tr == r)
{
SegmentTree[v] = m(SegmentTree[v], tl, tr, new_modification);
if (v < base_capacity) ModifierList[v] = new_modification;
}
else
{
size_t tm = (tl + tr) / 2;
assign_in(2*v, tl, tm, l, min(r,tm), new_modification);
assign_in(2*v+1, tm+1, tr, max(l,tm+1), r, new_modification);
SegmentTree[v] = g(SegmentTree[2*v], SegmentTree[2*v+1]);
}
}
}
/*
result_on_segment_in:
returns value on segment [l, r];
*/
TYPE result_on_segment_in
(
size_t v, size_t tl,
size_t tr, size_t l,
size_t r
)
{
if (l > r) return neutral;
else
{
if (l == tl && r == tr) return SegmentTree[v];
else
{
try_push(v, tl, tr);
size_t tm = (tl + tr) / 2;
return g(result_on_segment_in(v*2, tl, tm, l, min(r,tm)),
result_on_segment_in(v*2+1, tm+1, tr, max(l,tm+1), r));
}
}
}
/*
make_monoid_and_fill_rest:
- fills the unused space of array (which appears due to rounding of size of parental array)
with neutral elements.
- assigns the necessary values to the upper "vertexes" of the tree.
*/
void make_monoid_and_fill_rest
(
TYPE *NewTree,
const size_t &n,
TYPE f(const TYPE&, const TYPE&),
const TYPE &neutr,
TYPE modifier_function(const TYPE&, const size_t&, const size_t&, const MODIFICATION_TYPE&),
MODIFICATION_TYPE modification_combinator(const MODIFICATION_TYPE&, const MODIFICATION_TYPE&),
const MODIFICATION_TYPE &new_neutral_modifier
)
{
g = f;
m = modifier_function;
combine_modifications = modification_combinator;
neutral = neutr;
neutral_modifier = new_neutral_modifier;
for(size_t i = base_capacity+n; i < 2*base_capacity; ++i)
{
NewTree[i] = neutral;
}
for(size_t i = base_capacity-1; i > 0; --i)
{
NewTree[i] = g(NewTree[2*i], NewTree[2*i+1]);
ModifierList[i] = neutral_modifier;
}
ModifierList[0] = neutral_modifier;
SegmentTree = NewTree;
}
/*
fix_capacity:
Rounds base_capacity of the base array to closest upper power of 2.
*/
void fix_capacity(const size_t &base_array_size)
{
for (base_capacity = 1; base_capacity < base_array_size; base_capacity <<= 1);
}
public:
/*
##########################
#### PUBLIC FUNCTIONS ####
##########################
Definitions:
n - amount of elements in the parental array;
lb - binary logarithm.
Lowest level of the tree - parental array (segment of elements, which is a base of the tree)
and (if exists) unused space, filled with neutral elements.
construct:
Constructs the tree by copying elements of [begin; end) memory block into the segment tree,
and by building tree's structure using the given binary operation "f" and its neutral element "neutr".
Complexity: O(n).
*/
void construct
(
const TYPE *begin,
const TYPE *end,
TYPE f(const TYPE&, const TYPE&),
const TYPE neutr,
TYPE modifier_function(const TYPE&, const size_t&, const size_t&, const MODIFICATION_TYPE&),
MODIFICATION_TYPE modification_combinator(const MODIFICATION_TYPE&, const MODIFICATION_TYPE&),
const MODIFICATION_TYPE new_neutral_modifier
)
{
size_t base_size = end - begin;
fix_capacity(base_size);
TYPE *NewTree = new TYPE[base_capacity*2];
ModifierList = new MODIFICATION_TYPE[base_capacity];
for(size_t i = 0; i < base_size; ++i)
{
NewTree[base_capacity+i] = begin[i];
}
make_monoid_and_fill_rest(NewTree, base_size, f, neutr, modifier_function, modification_combinator, new_neutral_modifier);
}
/*
read_and_construct:
Constructs the tree by filling with it with elements, created by "preprocessing_function",
and by building tree's structure using the given binary operation "f" and its neutral element "neutr".
This method is useful for creating tree by giving preprocessing_function an ability to read
the data from the incoming stream, if the separate memorisation of the base array is not needed.
Complexity: O(n).
*/
void read_and_construct
(
const size_t amount_of_elements,
TYPE preprocessing_function(),
TYPE f(const TYPE&, const TYPE&),
const TYPE neutr,
TYPE modifier_function(const TYPE&, const size_t&, const size_t&, const MODIFICATION_TYPE&),
MODIFICATION_TYPE modification_combinator(const MODIFICATION_TYPE&, const MODIFICATION_TYPE&),
const MODIFICATION_TYPE new_neutral_modifier
)
{
fix_capacity(amount_of_elements);
TYPE *NewTree = new TYPE[base_capacity*2];
ModifierList = new MODIFICATION_TYPE[base_capacity];
for(size_t i = 0; i < amount_of_elements; ++i)
{
NewTree[base_capacity+i] = preprocessing_function();
}
make_monoid_and_fill_rest(NewTree, amount_of_elements, f, neutr, modifier_function, modification_combinator, new_neutral_modifier);
}
/*
assign:
Assigns new value to the element of base array with given index [i]
or modifies the given segment [l, r], relatively to the modifier value.
Complexity: O(lb(n))
*/
void assign(size_t i, const MODIFICATION_TYPE modifier)
{
assign_in(1, 0, base_capacity-1, i, i, modifier);
}
void assign(size_t l, size_t r, const MODIFICATION_TYPE modifier)
{
assign_in(1, 0, base_capacity-1, l, r, modifier);
}
/*
result_on_segment:
Returns value of operation on the given segment of parental array.
Complexity: O(lb(n)).
*/
TYPE result_on_segment(size_t l, size_t r)
{
return result_on_segment_in(1, 0, base_capacity-1, l, r);
}
};
int main()
{
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKdGVtcGxhdGUgPGNsYXNzIFRZUEUsIGNsYXNzIE1PRElGSUNBVElPTl9UWVBFPiBjbGFzcyBzZWdtZW50c190cmVlCnsKCVRZUEUgKlNlZ21lbnRUcmVlOwoJTU9ESUZJQ0FUSU9OX1RZUEUqIE1vZGlmaWVyTGlzdDsKCXNpemVfdCBiYXNlX2NhcGFjaXR5OwoJVFlQRSAoKmcpKGNvbnN0IFRZUEUmLCBjb25zdCBUWVBFJik7CglUWVBFICgqbSkoY29uc3QgVFlQRSYsIGNvbnN0IHNpemVfdCYsIGNvbnN0IHNpemVfdCYsIGNvbnN0IE1PRElGSUNBVElPTl9UWVBFJik7CglNT0RJRklDQVRJT05fVFlQRSAoKmNvbWJpbmVfbW9kaWZpY2F0aW9ucykoY29uc3QgTU9ESUZJQ0FUSU9OX1RZUEUmLCBjb25zdCBNT0RJRklDQVRJT05fVFlQRSYpOwoJVFlQRSBuZXV0cmFsOwoJTU9ESUZJQ0FUSU9OX1RZUEUgbmV1dHJhbF9tb2RpZmllcjsKCgkvKgoJVFlQRToKCQlUeXBlIG9mIGVsZW1lbnRzIGluIHRoZSB0cmVlLgoKCU1PRElGSUNBVElPTl9UWVBFOgoJCVNwZWNpYWwgdHlwZSwgd2hpY2ggYWxsb3dzIHRvIHN5bmNocm9uaXplIG1vZGlmaWNhdGlvbnMgb24gc2VnbWVudC4KCglTZWdtZW50VHJlZTogKHBvaW50ZXIpCgkJQXJyYXktYmFzZWQgdHJlZSBvZiBlbGVtZW50cy4KCgliYXNlX2NhcGFjaXR5OiAodW5zaWduZWQgaW50ZWdlciB2YWx1ZSkKCQlQYXJlbnRhbCBhcnJheSBzaXplLCByb3VuZGVkIHRvIHRoZSBjbG9zZXN0IHVwcGVyIHBvd2VyIG9mIDIuCgoJZzogKHBvaW50ZXIpCgkJUG9pbnRlciB0byB0aGUgZnVudGlvbiAoYXNzb2NpYXRpdmUgYmluYXJ5IG9wZXJhdGlvbiksIGFwcGxpZWQgb24gdGhlIGdpdmVuIGFycmF5IG9mIGVsZW1lbnRzLgoJCVdBUk5JTkc6IFRoZSBnaXZlbiBmdW5jdGlvbiBtdXN0IGJlIGFzc29jaWF0aXZlLiBUaGUgbW9ub2lkYWwgc3RydWN0dXJlIG9mIHRoZSB0cmVlIHdpbGwgYmUgcnVpbmVkIG90aGVyd2lzZS4KCgltOiAocG9pbnRlcikKCQlQb2ludGVyIHRvIHRoZSBmdW5jdGlvbiwgdXNlZCB0byBtb2RpZnkgc2VnbWVudHMgb2YgdGhlIHRyZWUuCgkKCWNvbWJpbmVfbW9kaWZpY2F0aW9uczogKHBvaW50ZXIpCgkJUG9pbnRlciB0byB0aGUgZnVuY3Rpb24sIHdoaWNoIGNvbWJpbmVzIG9sZCBhbmQgbmV3IG1vZGlmaWNhdGlvbnMgdG8gc3luY2hyb25pemUgdGhlbS4KCgluZXV0cmFsOiAoYXJyYXkgZWxlbWVudCkKCQlUaGUgdmFsdWUgb2YgZWxlbWVudCwgd2hpY2ggaXMgbmV1dHJhbCByZWxhdGl2ZWx5IHRvICJnIiBmdW5jdGlvbi4KCgluZXV0cmFsX21vZGlmaWVyOgoJCU1hcmtlciBvZiBub24tbW9kaWZpZWQgdmVydGV4ZXMuCgoJIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMKCSMjIyMgSU5ORVIgSEVMUEVSIEZVTkNUSU9OUyAjIyMjCgkjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIwoJdHJ5X3B1c2g6IHB1c2hlcyB0aGUgbW9kaWZpZXIgdmFsdWUgZnJvbSB2ZXJ0ZXggdG8gaXRzIGxlZnQgYW5kIHJpZ2h0IGxlYWYuCgkqLwoJdm9pZCB0cnlfcHVzaChzaXplX3QmIHYsIHNpemVfdCYgdGwsIHNpemVfdCYgdHIpCgl7CgkJaWYgKHYgPCBiYXNlX2NhcGFjaXR5KSBpZiAoTW9kaWZpZXJMaXN0W3ZdICE9IG5ldXRyYWxfbW9kaWZpZXIpCgkJewoJCQlzaXplX3QgbWlkID0gKHRyK3RsKS8yLCBpID0gMip2OwoJCQlTZWdtZW50VHJlZVtpXSA9IG0oU2VnbWVudFRyZWVbaV0sIHRsLCBtaWQsIE1vZGlmaWVyTGlzdFt2XSk7CgkJCVNlZ21lbnRUcmVlW2krMV0gPSBtKFNlZ21lbnRUcmVlW2krMV0sICsrbWlkLCB0ciwgTW9kaWZpZXJMaXN0W3ZdKTsKCgkJCWlmIChpKzEgPCBiYXNlX2NhcGFjaXR5KQoJCQl7CgkJCQlNb2RpZmllckxpc3RbaV0gPSBjb21iaW5lX21vZGlmaWNhdGlvbnMoTW9kaWZpZXJMaXN0W2ldLCBNb2RpZmllckxpc3Rbdl0pOwoJCQkJTW9kaWZpZXJMaXN0W2krMV0gPSBjb21iaW5lX21vZGlmaWNhdGlvbnMoTW9kaWZpZXJMaXN0W2krMV0sIE1vZGlmaWVyTGlzdFt2XSk7CgkJCX0KCgkJCU1vZGlmaWVyTGlzdFt2XSA9IG5ldXRyYWxfbW9kaWZpZXI7CgkJfQoJfQoKCS8qCglhc3NpZ25faW46CgkJYXNzaWducyBhIG5ldyB2YWx1ZXMgdG8gdGhlIHZlcnRleGVzIG9mIHRoZSB0cmVlLAoJCXdoaWNoIGFyZSByZXNwb25zaWJsZSBmb3IgdGhlIHZhbHVlIG9mIFtsOyByXSBzZWdtZW50LgoJKi8KCXZvaWQgYXNzaWduX2luCgkoCgkJc2l6ZV90IHYsCgkJc2l6ZV90IHRsLCBzaXplX3QgdHIsCgkJc2l6ZV90IGwsIHNpemVfdCByLAoJCWNvbnN0IE1PRElGSUNBVElPTl9UWVBFJiBuZXdfbW9kaWZpY2F0aW9uCgkpCgl7CgkJaWYgKGwgPD0gcikKCQl7CgkJCXRyeV9wdXNoKHYsIHRsLCB0cik7CgkJCWlmIChsID09IHRsICYmIHRyID09IHIpCgkJCXsKCQkJCVNlZ21lbnRUcmVlW3ZdID0gbShTZWdtZW50VHJlZVt2XSwgdGwsIHRyLCBuZXdfbW9kaWZpY2F0aW9uKTsKCQkJCWlmICh2IDwgYmFzZV9jYXBhY2l0eSkgTW9kaWZpZXJMaXN0W3ZdID0gbmV3X21vZGlmaWNhdGlvbjsKCQkJfQoJCQllbHNlCgkJCXsKCQkJCXNpemVfdCB0bSA9ICh0bCArIHRyKSAvIDI7CgkJCQkKCQkJCWFzc2lnbl9pbigyKnYsIHRsLCB0bSwgbCwgbWluKHIsdG0pLCBuZXdfbW9kaWZpY2F0aW9uKTsKCQkJCWFzc2lnbl9pbigyKnYrMSwgdG0rMSwgdHIsIG1heChsLHRtKzEpLCByLCBuZXdfbW9kaWZpY2F0aW9uKTsKCQkJCQoJCQkJU2VnbWVudFRyZWVbdl0gPSBnKFNlZ21lbnRUcmVlWzIqdl0sIFNlZ21lbnRUcmVlWzIqdisxXSk7CgkJCX0KCQl9Cgl9CgoJLyoKCXJlc3VsdF9vbl9zZWdtZW50X2luOgoJCXJldHVybnMgdmFsdWUgb24gc2VnbWVudCBbbCwgcl07CgkqLwoJVFlQRSByZXN1bHRfb25fc2VnbWVudF9pbgoJKAoJCXNpemVfdCB2LCBzaXplX3QgdGwsCgkJc2l6ZV90IHRyLCBzaXplX3QgbCwKCQlzaXplX3QgcgoJKQoJewoJCWlmIChsID4gcikgcmV0dXJuIG5ldXRyYWw7CgkJZWxzZQoJCXsKCQkJaWYgKGwgPT0gdGwgJiYgciA9PSB0cikgcmV0dXJuIFNlZ21lbnRUcmVlW3ZdOwoJCQllbHNlCgkJCXsKCQkJCXRyeV9wdXNoKHYsIHRsLCB0cik7CgkJCQlzaXplX3QgdG0gPSAodGwgKyB0cikgLyAyOwoJCQkJcmV0dXJuIGcocmVzdWx0X29uX3NlZ21lbnRfaW4odioyLCB0bCwgdG0sIGwsIG1pbihyLHRtKSksCgkJCQlyZXN1bHRfb25fc2VnbWVudF9pbih2KjIrMSwgdG0rMSwgdHIsIG1heChsLHRtKzEpLCByKSk7CgkJCX0KCQl9Cgl9CgoJLyoKCW1ha2VfbW9ub2lkX2FuZF9maWxsX3Jlc3Q6CgkJLSBmaWxscyB0aGUgdW51c2VkIHNwYWNlIG9mIGFycmF5ICh3aGljaCBhcHBlYXJzIGR1ZSB0byByb3VuZGluZyBvZiBzaXplIG9mIHBhcmVudGFsIGFycmF5KQoJCXdpdGggbmV1dHJhbCBlbGVtZW50cy4KCQktIGFzc2lnbnMgdGhlIG5lY2Vzc2FyeSB2YWx1ZXMgdG8gdGhlIHVwcGVyICJ2ZXJ0ZXhlcyIgb2YgdGhlIHRyZWUuCgkqLwoJdm9pZCBtYWtlX21vbm9pZF9hbmRfZmlsbF9yZXN0CgkoCgkJVFlQRSAqTmV3VHJlZSwKCQljb25zdCBzaXplX3QgJm4sCgkJVFlQRSBmKGNvbnN0IFRZUEUmLCBjb25zdCBUWVBFJiksCgkJY29uc3QgVFlQRSAmbmV1dHIsCgkJVFlQRSBtb2RpZmllcl9mdW5jdGlvbihjb25zdCBUWVBFJiwgY29uc3Qgc2l6ZV90JiwgY29uc3Qgc2l6ZV90JiwgY29uc3QgTU9ESUZJQ0FUSU9OX1RZUEUmKSwKCQlNT0RJRklDQVRJT05fVFlQRSBtb2RpZmljYXRpb25fY29tYmluYXRvcihjb25zdCBNT0RJRklDQVRJT05fVFlQRSYsIGNvbnN0IE1PRElGSUNBVElPTl9UWVBFJiksCgkJY29uc3QgTU9ESUZJQ0FUSU9OX1RZUEUgJm5ld19uZXV0cmFsX21vZGlmaWVyCgkpCgl7CgkJZyA9IGY7CgkJbSA9IG1vZGlmaWVyX2Z1bmN0aW9uOwoJCWNvbWJpbmVfbW9kaWZpY2F0aW9ucyA9IG1vZGlmaWNhdGlvbl9jb21iaW5hdG9yOwoJCW5ldXRyYWwgPSBuZXV0cjsKCQluZXV0cmFsX21vZGlmaWVyID0gbmV3X25ldXRyYWxfbW9kaWZpZXI7CgkJZm9yKHNpemVfdCBpID0gYmFzZV9jYXBhY2l0eStuOyBpIDwgMipiYXNlX2NhcGFjaXR5OyArK2kpCgkJewoJCQlOZXdUcmVlW2ldID0gbmV1dHJhbDsKCQl9CgkJZm9yKHNpemVfdCBpID0gYmFzZV9jYXBhY2l0eS0xOyBpID4gMDsgLS1pKQoJCXsKCQkJTmV3VHJlZVtpXSA9IGcoTmV3VHJlZVsyKmldLCBOZXdUcmVlWzIqaSsxXSk7CgkJCU1vZGlmaWVyTGlzdFtpXSA9IG5ldXRyYWxfbW9kaWZpZXI7CgkJfQoJCU1vZGlmaWVyTGlzdFswXSA9IG5ldXRyYWxfbW9kaWZpZXI7CgkJU2VnbWVudFRyZWUgPSBOZXdUcmVlOwoJfQoKCS8qCglmaXhfY2FwYWNpdHk6CgkJUm91bmRzIGJhc2VfY2FwYWNpdHkgb2YgdGhlIGJhc2UgYXJyYXkgdG8gY2xvc2VzdCB1cHBlciBwb3dlciBvZiAyLgoJKi8KCXZvaWQgZml4X2NhcGFjaXR5KGNvbnN0IHNpemVfdCAmYmFzZV9hcnJheV9zaXplKQoJewoJCWZvciAoYmFzZV9jYXBhY2l0eSA9IDE7IGJhc2VfY2FwYWNpdHkgPCBiYXNlX2FycmF5X3NpemU7IGJhc2VfY2FwYWNpdHkgPDw9IDEpOwoJfQoKCXB1YmxpYzoKCS8qCgkjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIwoJIyMjIyBQVUJMSUMgRlVOQ1RJT05TICMjIyMKCSMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjCglEZWZpbml0aW9uczoKCQluIC0gYW1vdW50IG9mIGVsZW1lbnRzIGluIHRoZSBwYXJlbnRhbCBhcnJheTsKCQlsYiAtIGJpbmFyeSBsb2dhcml0aG0uCgkJTG93ZXN0IGxldmVsIG9mIHRoZSB0cmVlIC0gcGFyZW50YWwgYXJyYXkgKHNlZ21lbnQgb2YgZWxlbWVudHMsIHdoaWNoIGlzIGEgYmFzZSBvZiB0aGUgdHJlZSkKCQlhbmQgKGlmIGV4aXN0cykgdW51c2VkIHNwYWNlLCBmaWxsZWQgd2l0aCBuZXV0cmFsIGVsZW1lbnRzLgoKCWNvbnN0cnVjdDoKCQlDb25zdHJ1Y3RzIHRoZSB0cmVlIGJ5IGNvcHlpbmcgZWxlbWVudHMgb2YgW2JlZ2luOyBlbmQpIG1lbW9yeSBibG9jayBpbnRvIHRoZSBzZWdtZW50IHRyZWUsCgkJYW5kIGJ5IGJ1aWxkaW5nIHRyZWUncyBzdHJ1Y3R1cmUgdXNpbmcgdGhlIGdpdmVuIGJpbmFyeSBvcGVyYXRpb24gImYiIGFuZCBpdHMgbmV1dHJhbCBlbGVtZW50ICJuZXV0ciIuCgkJQ29tcGxleGl0eTogTyhuKS4KCSovCgl2b2lkIGNvbnN0cnVjdAoJKAoJCWNvbnN0IFRZUEUgKmJlZ2luLAoJCWNvbnN0IFRZUEUgKmVuZCwKCQlUWVBFIGYoY29uc3QgVFlQRSYsIGNvbnN0IFRZUEUmKSwKCQljb25zdCBUWVBFIG5ldXRyLAoJCVRZUEUgbW9kaWZpZXJfZnVuY3Rpb24oY29uc3QgVFlQRSYsIGNvbnN0IHNpemVfdCYsIGNvbnN0IHNpemVfdCYsIGNvbnN0IE1PRElGSUNBVElPTl9UWVBFJiksCgkJTU9ESUZJQ0FUSU9OX1RZUEUgbW9kaWZpY2F0aW9uX2NvbWJpbmF0b3IoY29uc3QgTU9ESUZJQ0FUSU9OX1RZUEUmLCBjb25zdCBNT0RJRklDQVRJT05fVFlQRSYpLAoJCWNvbnN0IE1PRElGSUNBVElPTl9UWVBFIG5ld19uZXV0cmFsX21vZGlmaWVyCgkpCgl7CgkJc2l6ZV90IGJhc2Vfc2l6ZSA9IGVuZCAtIGJlZ2luOwoJCWZpeF9jYXBhY2l0eShiYXNlX3NpemUpOwoJCVRZUEUgKk5ld1RyZWUgPSBuZXcgVFlQRVtiYXNlX2NhcGFjaXR5KjJdOwoJCU1vZGlmaWVyTGlzdCA9IG5ldyBNT0RJRklDQVRJT05fVFlQRVtiYXNlX2NhcGFjaXR5XTsKCQlmb3Ioc2l6ZV90IGkgPSAwOyBpIDwgYmFzZV9zaXplOyArK2kpCgkJewoJCQlOZXdUcmVlW2Jhc2VfY2FwYWNpdHkraV0gPSBiZWdpbltpXTsKCQl9CgkJbWFrZV9tb25vaWRfYW5kX2ZpbGxfcmVzdChOZXdUcmVlLCBiYXNlX3NpemUsIGYsIG5ldXRyLCBtb2RpZmllcl9mdW5jdGlvbiwgbW9kaWZpY2F0aW9uX2NvbWJpbmF0b3IsIG5ld19uZXV0cmFsX21vZGlmaWVyKTsKCX0KCgkvKgoJcmVhZF9hbmRfY29uc3RydWN0OgoJCUNvbnN0cnVjdHMgdGhlIHRyZWUgYnkgZmlsbGluZyB3aXRoIGl0IHdpdGggZWxlbWVudHMsIGNyZWF0ZWQgYnkgInByZXByb2Nlc3NpbmdfZnVuY3Rpb24iLAoJCWFuZCBieSBidWlsZGluZyB0cmVlJ3Mgc3RydWN0dXJlIHVzaW5nIHRoZSBnaXZlbiBiaW5hcnkgb3BlcmF0aW9uICJmIiBhbmQgaXRzIG5ldXRyYWwgZWxlbWVudCAibmV1dHIiLgoJCVRoaXMgbWV0aG9kIGlzIHVzZWZ1bCBmb3IgY3JlYXRpbmcgdHJlZSBieSBnaXZpbmcgcHJlcHJvY2Vzc2luZ19mdW5jdGlvbiBhbiBhYmlsaXR5IHRvIHJlYWQKCQl0aGUgZGF0YSBmcm9tIHRoZSBpbmNvbWluZyBzdHJlYW0sIGlmIHRoZSBzZXBhcmF0ZSBtZW1vcmlzYXRpb24gb2YgdGhlIGJhc2UgYXJyYXkgaXMgbm90IG5lZWRlZC4KCQlDb21wbGV4aXR5OiBPKG4pLgoJKi8KCXZvaWQgcmVhZF9hbmRfY29uc3RydWN0CgkoCgkJY29uc3Qgc2l6ZV90IGFtb3VudF9vZl9lbGVtZW50cywKCQlUWVBFIHByZXByb2Nlc3NpbmdfZnVuY3Rpb24oKSwKCQlUWVBFIGYoY29uc3QgVFlQRSYsIGNvbnN0IFRZUEUmKSwKCQljb25zdCBUWVBFIG5ldXRyLAoJCVRZUEUgbW9kaWZpZXJfZnVuY3Rpb24oY29uc3QgVFlQRSYsIGNvbnN0IHNpemVfdCYsIGNvbnN0IHNpemVfdCYsIGNvbnN0IE1PRElGSUNBVElPTl9UWVBFJiksCgkJTU9ESUZJQ0FUSU9OX1RZUEUgbW9kaWZpY2F0aW9uX2NvbWJpbmF0b3IoY29uc3QgTU9ESUZJQ0FUSU9OX1RZUEUmLCBjb25zdCBNT0RJRklDQVRJT05fVFlQRSYpLAoJCWNvbnN0IE1PRElGSUNBVElPTl9UWVBFIG5ld19uZXV0cmFsX21vZGlmaWVyCgkpCgl7CgkJZml4X2NhcGFjaXR5KGFtb3VudF9vZl9lbGVtZW50cyk7CgkJVFlQRSAqTmV3VHJlZSA9IG5ldyBUWVBFW2Jhc2VfY2FwYWNpdHkqMl07CgkJTW9kaWZpZXJMaXN0ID0gbmV3IE1PRElGSUNBVElPTl9UWVBFW2Jhc2VfY2FwYWNpdHldOwoJCWZvcihzaXplX3QgaSA9IDA7IGkgPCBhbW91bnRfb2ZfZWxlbWVudHM7ICsraSkKCQl7CgkJCU5ld1RyZWVbYmFzZV9jYXBhY2l0eStpXSA9IHByZXByb2Nlc3NpbmdfZnVuY3Rpb24oKTsKCQl9CgkJbWFrZV9tb25vaWRfYW5kX2ZpbGxfcmVzdChOZXdUcmVlLCBhbW91bnRfb2ZfZWxlbWVudHMsIGYsIG5ldXRyLCBtb2RpZmllcl9mdW5jdGlvbiwgbW9kaWZpY2F0aW9uX2NvbWJpbmF0b3IsIG5ld19uZXV0cmFsX21vZGlmaWVyKTsKCX0KCgkvKgoJYXNzaWduOgoJCUFzc2lnbnMgbmV3IHZhbHVlIHRvIHRoZSBlbGVtZW50IG9mIGJhc2UgYXJyYXkgd2l0aCBnaXZlbiBpbmRleCBbaV0KCQlvciBtb2RpZmllcyB0aGUgZ2l2ZW4gc2VnbWVudCBbbCwgcl0sIHJlbGF0aXZlbHkgdG8gdGhlIG1vZGlmaWVyIHZhbHVlLgoJCUNvbXBsZXhpdHk6IE8obGIobikpCgkqLwoJdm9pZCBhc3NpZ24oc2l6ZV90IGksIGNvbnN0IE1PRElGSUNBVElPTl9UWVBFIG1vZGlmaWVyKQoJewoJCWFzc2lnbl9pbigxLCAwLCBiYXNlX2NhcGFjaXR5LTEsIGksIGksIG1vZGlmaWVyKTsKCX0KCgl2b2lkIGFzc2lnbihzaXplX3QgbCwgc2l6ZV90IHIsIGNvbnN0IE1PRElGSUNBVElPTl9UWVBFIG1vZGlmaWVyKQoJewoJCWFzc2lnbl9pbigxLCAwLCBiYXNlX2NhcGFjaXR5LTEsIGwsIHIsIG1vZGlmaWVyKTsKCX0KCgkvKgoJcmVzdWx0X29uX3NlZ21lbnQ6CgkJUmV0dXJucyB2YWx1ZSBvZiBvcGVyYXRpb24gb24gdGhlIGdpdmVuIHNlZ21lbnQgb2YgcGFyZW50YWwgYXJyYXkuCgkJQ29tcGxleGl0eTogTyhsYihuKSkuCgkqLwoJVFlQRSByZXN1bHRfb25fc2VnbWVudChzaXplX3QgbCwgc2l6ZV90IHIpCgl7CgkJcmV0dXJuIHJlc3VsdF9vbl9zZWdtZW50X2luKDEsIDAsIGJhc2VfY2FwYWNpdHktMSwgbCwgcik7Cgl9Cn07CgppbnQgbWFpbigpCnsKCXJldHVybiAwOwp9