/// 2-3 Tree
/// Reference: https://e...content-available-to-author-only...a.org/wiki/2%E2%80%933_tree
/// https://w...content-available-to-author-only...e.net/sandpoonia/23-tree
/// Verified by: ARC061-D (http://a...content-available-to-author-only...r.jp/submissions/1243868)
#[derive(Clone, Debug)]
enum TwoThreeTree<T> {
Tip,
Two(
usize, // size
T, // value
Box<TwoThreeTree<T>>, // left
Box<TwoThreeTree<T>>, // right
),
Three(
usize, // size
T, // val1
T, // val2
Box<TwoThreeTree<T>>, // left
Box<TwoThreeTree<T>>, // middle
Box<TwoThreeTree<T>>, // right
),
}
impl<T: Ord> TwoThreeTree<T> {
pub fn new() -> Self {
TwoThreeTree::Tip
}
fn size(&self) -> usize {
use TwoThreeTree::*;
match *self {
Tip => 0,
Two(sz, _, _, _) => sz,
Three(sz, _, _, _, _, _) => sz,
}
}
fn leaf_one(x: T) -> Self {
use TwoThreeTree::*;
Two(1, x, Box::new(Tip), Box::new(Tip))
}
fn leaf_two(x: T, y: T) -> Self {
use TwoThreeTree::*;
Three(2, x, y, Box::new(Tip), Box::new(Tip), Box::new(Tip))
}
fn node_two(x: T, left: Self, right: Self) -> Self {
TwoThreeTree::Two(left.size() + right.size() + 1, x,
Box::new(left), Box::new(right))
}
fn node_three(x: T, y: T, left: Self, middle: Self, right: Self) -> Self {
TwoThreeTree::Three(left.size() + middle.size() + right.size() + 2,
x, y,
Box::new(left), Box::new(middle), Box::new(right))
}
fn divide_four(t1: Self, v1: T, t2: Self, v2: T,
t3: Self, v3: T, t4: Self) -> (Self, Self, T) {
(Self::node_two(v1, t1, t2), Self::node_two(v3, t3, t4), v2)
}
// Ok(x) -> ordinary tree
// Err((t1, t2, v)) -> propagating v, whilst dividing the tree into t1, t2
fn insert_sub(self, x: T) -> Result<Self, (Self, Self, T)> {
use TwoThreeTree::*;
match self {
Tip => Ok(Self::leaf_one(x)),
Two(1, val, _, _) => // leaf
Ok(match x.cmp(&val) {
std::cmp::Ordering::Equal => Self::leaf_one(val),
std::cmp::Ordering::Less => Self::leaf_two(x, val),
std::cmp::Ordering::Greater => Self::leaf_two(val, x),
}),
Three(2, val1, val2, _, _, _) => { // leaf
// $a, $b, $c should be increasing in this order.
macro_rules! err_3 {
($a:expr, $b:expr, $c:expr) => {
Err((Self::leaf_one($a),
Self::leaf_one($c),
$b))
}
}
if val1 == x || val2 == x {
Ok(Self::leaf_two(val1, val2))
} else if x < val1 {
err_3!(x, val1, val2)
} else if x < val2 {
err_3!(val1, x, val2)
} else {
err_3!(val1, val2, x)
}
}
Two(size, val, left, right) => {
match x.cmp(&val) {
std::cmp::Ordering::Equal =>
Ok(Two(size, val, left, right)),
std::cmp::Ordering::Less => {
match left.insert_sub(x) {
Ok(t) => Ok(Self::node_two(val, t, *right)),
Err((t1, t2, sub_up)) =>
Ok(Self::node_three(sub_up, val,
t1, t2, *right)),
}
},
std::cmp::Ordering::Greater => {
match right.insert_sub(x) {
Ok(t) => Ok(Self::node_two(val, *left, t)),
Err((t1, t2, sub_up)) =>
Ok(Self::node_three(val, sub_up,
*left, t1, t2)),
}
},
}
}
Three(size, val1, val2, left, middle, right) => {
if x == val1 || x == val2 {
return Ok(Three(size, val1, val2, left, middle, right));
}
if x < val1 {
match left.insert_sub(x) {
Ok(sub_tr) =>
Ok(Self::node_three(val1, val2,
sub_tr, *middle, *right)),
Err((t1, t2, sub_up)) => {
let (t1, t2, v) = Self::divide_four(
t1, sub_up, t2, val1,
*middle, val2, *right);
Err((t1, t2, v))
},
}
} else if x < val2 {
match middle.insert_sub(x) {
Ok(sub_tr) =>
Ok(Self::node_three(val1, val2,
*left, sub_tr, *right)),
Err((t1, t2, sub_up)) => {
let (t1, t2, v) = Self::divide_four(
*left, val1, t1, sub_up,
t2, val2, *right);
Err((t1, t2, v))
},
}
} else {
match right.insert_sub(x) {
Ok(sub_tr) =>
Ok(Self::node_three(val1, val2,
*left, *middle, sub_tr)),
Err((t1, t2, sub_up)) => {
let (t1, t2, v) = Self::divide_four(
*left, val1, *middle, val2,
t1, sub_up, t2);
Err((t1, t2, v))
},
}
}
}
}
}
fn insert(self, x: T) -> Self {
match self.insert_sub(x) {
Ok(t) => t,
Err((t1, t2, v)) =>
Self::node_two(v, t1, t2),
}
}
fn into_vec_sub(self, ret: &mut Vec<T>) {
use TwoThreeTree::*;
match self {
Tip => (),
Two(_, val, left, right) => {
left.into_vec_sub(ret);
ret.push(val);
right.into_vec_sub(ret);
},
Three(_, val1, val2, left, middle, right) => {
left.into_vec_sub(ret);
ret.push(val1);
middle.into_vec_sub(ret);
ret.push(val2);
right.into_vec_sub(ret);
},
}
}
pub fn find_index(&self, x: &T) -> (usize, bool) {
use TwoThreeTree::*;
match *self {
Tip => (0, false),
Two(_size, ref v, ref left, ref right) => {
match x.cmp(v) {
std::cmp::Ordering::Equal => (left.size(), true),
std::cmp::Ordering::Less => left.find_index(x),
std::cmp::Ordering::Greater => {
let (res, found) = right.find_index(x);
(res + left.size() + 1, found)
},
}
},
Three(_size, ref v1, ref v2, ref left, ref middle, ref right) => {
if x == v1 {
return (left.size(), true);
}
if x == v2 {
return (left.size() + middle.size() + 1, true);
}
if x < v1 {
return left.find_index(x);
}
if x < v2 {
let (res, found) = middle.find_index(x);
return (left.size() + 1 + res, found);
}
let (res, found) = right.find_index(x);
return (left.size() + middle.size() + 2 + res, found);
}
}
}
pub fn into_vec(self) -> Vec<T> {
let mut ret = Vec::with_capacity(self.size());
self.into_vec_sub(&mut ret);
ret
}
}
fn depth<T>(t: &TwoThreeTree<T>) -> usize {
use TwoThreeTree::*;
match *t {
Tip => 0,
Two(_, _, ref left, _) => 1 + depth(left),
Three(_, _, _, ref left, _, _) => 1 + depth(left),
}
}
fn main() {
let mut bst = TwoThreeTree::new();
let mut seed: i64 = 0xdeadc0de;
let mut next = || {
seed = seed.wrapping_mul(0x12345678deadc0d1).wrapping_add(0x1551);
seed
};
const N: usize = 1000000;
for _ in 0 .. 1000 { next(); }
let mut cur_depth = 0;
for i in 0 .. N {
let elem = (next() & 0xffff_ffff) as usize;
bst = bst.insert(elem);
let dep = depth(&bst);
if cur_depth != dep {
println!("i = {}, depth = {}", i, dep);
cur_depth = dep;
}
}
}
Ly8vIDItMyBUcmVlCi8vLyBSZWZlcmVuY2U6IGh0dHBzOi8vZS4uLmNvbnRlbnQtYXZhaWxhYmxlLXRvLWF1dGhvci1vbmx5Li4uYS5vcmcvd2lraS8yJUUyJTgwJTkzM190cmVlCi8vLyBodHRwczovL3cuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLmUubmV0L3NhbmRwb29uaWEvMjMtdHJlZQovLy8gVmVyaWZpZWQgYnk6IEFSQzA2MS1EIChodHRwOi8vYS4uLmNvbnRlbnQtYXZhaWxhYmxlLXRvLWF1dGhvci1vbmx5Li4uci5qcC9zdWJtaXNzaW9ucy8xMjQzODY4KQojW2Rlcml2ZShDbG9uZSwgRGVidWcpXQplbnVtIFR3b1RocmVlVHJlZTxUPiB7CiAgICBUaXAsCiAgICBUd28oCiAgICAgICAgdXNpemUsIC8vIHNpemUKICAgICAgICBULCAvLyB2YWx1ZQogICAgICAgIEJveDxUd29UaHJlZVRyZWU8VD4+LCAvLyBsZWZ0CiAgICAgICAgQm94PFR3b1RocmVlVHJlZTxUPj4sIC8vIHJpZ2h0CiAgICApLAogICAgVGhyZWUoCiAgICAgICAgdXNpemUsIC8vIHNpemUKICAgICAgICBULCAvLyB2YWwxCiAgICAgICAgVCwgLy8gdmFsMgogICAgICAgIEJveDxUd29UaHJlZVRyZWU8VD4+LCAvLyBsZWZ0CiAgICAgICAgQm94PFR3b1RocmVlVHJlZTxUPj4sIC8vIG1pZGRsZQogICAgICAgIEJveDxUd29UaHJlZVRyZWU8VD4+LCAvLyByaWdodAogICAgKSwKfQoKaW1wbDxUOiBPcmQ+IFR3b1RocmVlVHJlZTxUPiB7CiAgICBwdWIgZm4gbmV3KCkgLT4gU2VsZiB7CiAgICAgICAgVHdvVGhyZWVUcmVlOjpUaXAKICAgIH0KICAgIGZuIHNpemUoJnNlbGYpIC0+IHVzaXplIHsKICAgICAgICB1c2UgVHdvVGhyZWVUcmVlOjoqOwogICAgICAgIG1hdGNoICpzZWxmIHsKICAgICAgICAgICAgVGlwID0+IDAsCiAgICAgICAgICAgIFR3byhzeiwgXywgXywgXykgPT4gc3osCiAgICAgICAgICAgIFRocmVlKHN6LCBfLCBfLCBfLCBfLCBfKSA9PiBzeiwKICAgICAgICB9CiAgICB9CiAgICBmbiBsZWFmX29uZSh4OiBUKSAtPiBTZWxmIHsKICAgICAgICB1c2UgVHdvVGhyZWVUcmVlOjoqOwogICAgICAgIFR3bygxLCB4LCBCb3g6Om5ldyhUaXApLCBCb3g6Om5ldyhUaXApKQogICAgfQogICAgZm4gbGVhZl90d28oeDogVCwgeTogVCkgLT4gU2VsZiB7CiAgICAgICAgdXNlIFR3b1RocmVlVHJlZTo6KjsKICAgICAgICBUaHJlZSgyLCB4LCB5LCBCb3g6Om5ldyhUaXApLCBCb3g6Om5ldyhUaXApLCBCb3g6Om5ldyhUaXApKQogICAgfQogICAgZm4gbm9kZV90d28oeDogVCwgbGVmdDogU2VsZiwgcmlnaHQ6IFNlbGYpIC0+IFNlbGYgewogICAgICAgIFR3b1RocmVlVHJlZTo6VHdvKGxlZnQuc2l6ZSgpICsgcmlnaHQuc2l6ZSgpICsgMSwgeCwKICAgICAgICAgICAgICAgICAgICAgICAgICBCb3g6Om5ldyhsZWZ0KSwgQm94OjpuZXcocmlnaHQpKQogICAgfQogICAgZm4gbm9kZV90aHJlZSh4OiBULCB5OiBULCBsZWZ0OiBTZWxmLCBtaWRkbGU6IFNlbGYsIHJpZ2h0OiBTZWxmKSAtPiBTZWxmIHsKICAgICAgICBUd29UaHJlZVRyZWU6OlRocmVlKGxlZnQuc2l6ZSgpICsgbWlkZGxlLnNpemUoKSArIHJpZ2h0LnNpemUoKSArIDIsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICB4LCB5LAogICAgICAgICAgICAgICAgICAgICAgICAgICAgQm94OjpuZXcobGVmdCksIEJveDo6bmV3KG1pZGRsZSksIEJveDo6bmV3KHJpZ2h0KSkKICAgIH0KICAgIGZuIGRpdmlkZV9mb3VyKHQxOiBTZWxmLCB2MTogVCwgdDI6IFNlbGYsIHYyOiBULAogICAgICAgICAgICAgICAgICAgICAgIHQzOiBTZWxmLCB2MzogVCwgdDQ6IFNlbGYpIC0+IChTZWxmLCBTZWxmLCBUKSB7CiAgICAgICAgKFNlbGY6Om5vZGVfdHdvKHYxLCB0MSwgdDIpLCBTZWxmOjpub2RlX3R3byh2MywgdDMsIHQ0KSwgdjIpCiAgICB9CiAgICAvLyBPayh4KSAtPiBvcmRpbmFyeSB0cmVlCiAgICAvLyBFcnIoKHQxLCB0MiwgdikpIC0+IHByb3BhZ2F0aW5nIHYsIHdoaWxzdCBkaXZpZGluZyB0aGUgdHJlZSBpbnRvIHQxLCB0MgogICAgZm4gaW5zZXJ0X3N1YihzZWxmLCB4OiBUKSAtPiBSZXN1bHQ8U2VsZiwgKFNlbGYsIFNlbGYsIFQpPiB7CiAgICAgICAgdXNlIFR3b1RocmVlVHJlZTo6KjsKICAgICAgICBtYXRjaCBzZWxmIHsKICAgICAgICAgICAgVGlwID0+IE9rKFNlbGY6OmxlYWZfb25lKHgpKSwKICAgICAgICAgICAgVHdvKDEsIHZhbCwgXywgXykgPT4gLy8gbGVhZgogICAgICAgICAgICAgICAgT2sobWF0Y2ggeC5jbXAoJnZhbCkgewogICAgICAgICAgICAgICAgICAgIHN0ZDo6Y21wOjpPcmRlcmluZzo6RXF1YWwgPT4gU2VsZjo6bGVhZl9vbmUodmFsKSwKICAgICAgICAgICAgICAgICAgICBzdGQ6OmNtcDo6T3JkZXJpbmc6Okxlc3MgPT4gU2VsZjo6bGVhZl90d28oeCwgdmFsKSwKICAgICAgICAgICAgICAgICAgICBzdGQ6OmNtcDo6T3JkZXJpbmc6OkdyZWF0ZXIgPT4gU2VsZjo6bGVhZl90d28odmFsLCB4KSwKICAgICAgICAgICAgICAgIH0pLAogICAgICAgICAgICBUaHJlZSgyLCB2YWwxLCB2YWwyLCBfLCBfLCBfKSA9PiB7IC8vIGxlYWYKICAgICAgICAgICAgICAgIC8vICRhLCAkYiwgJGMgc2hvdWxkIGJlIGluY3JlYXNpbmcgaW4gdGhpcyBvcmRlci4KICAgICAgICAgICAgICAgIG1hY3JvX3J1bGVzISBlcnJfMyB7CiAgICAgICAgICAgICAgICAgICAgKCRhOmV4cHIsICRiOmV4cHIsICRjOmV4cHIpID0+IHsKICAgICAgICAgICAgICAgICAgICAgICAgRXJyKChTZWxmOjpsZWFmX29uZSgkYSksCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgU2VsZjo6bGVhZl9vbmUoJGMpLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICRiKSkKICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBpZiB2YWwxID09IHggfHwgdmFsMiA9PSB4IHsKICAgICAgICAgICAgICAgICAgICBPayhTZWxmOjpsZWFmX3R3byh2YWwxLCB2YWwyKSkKICAgICAgICAgICAgICAgIH0gZWxzZSBpZiB4IDwgdmFsMSB7CiAgICAgICAgICAgICAgICAgICAgZXJyXzMhKHgsIHZhbDEsIHZhbDIpCiAgICAgICAgICAgICAgICB9IGVsc2UgaWYgeCA8IHZhbDIgewogICAgICAgICAgICAgICAgICAgIGVycl8zISh2YWwxLCB4LCB2YWwyKQogICAgICAgICAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgICAgICAgICBlcnJfMyEodmFsMSwgdmFsMiwgeCkKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgICAgICBUd28oc2l6ZSwgdmFsLCBsZWZ0LCByaWdodCkgPT4gewogICAgICAgICAgICAgICAgbWF0Y2ggeC5jbXAoJnZhbCkgewogICAgICAgICAgICAgICAgICAgIHN0ZDo6Y21wOjpPcmRlcmluZzo6RXF1YWwgPT4gCiAgICAgICAgICAgICAgICAgICAgICAgIE9rKFR3byhzaXplLCB2YWwsIGxlZnQsIHJpZ2h0KSksCiAgICAgICAgICAgICAgICAgICAgc3RkOjpjbXA6Ok9yZGVyaW5nOjpMZXNzID0+IHsKICAgICAgICAgICAgICAgICAgICAgICAgbWF0Y2ggbGVmdC5pbnNlcnRfc3ViKHgpIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIE9rKHQpID0+IE9rKFNlbGY6Om5vZGVfdHdvKHZhbCwgdCwgKnJpZ2h0KSksCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBFcnIoKHQxLCB0Miwgc3ViX3VwKSkgPT4KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBPayhTZWxmOjpub2RlX3RocmVlKHN1Yl91cCwgdmFsLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgdDEsIHQyLCAqcmlnaHQpKSwKICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgIH0sCiAgICAgICAgICAgICAgICAgICAgc3RkOjpjbXA6Ok9yZGVyaW5nOjpHcmVhdGVyID0+IHsKICAgICAgICAgICAgICAgICAgICAgICAgbWF0Y2ggcmlnaHQuaW5zZXJ0X3N1Yih4KSB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBPayh0KSA9PiBPayhTZWxmOjpub2RlX3R3byh2YWwsICpsZWZ0LCB0KSksCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBFcnIoKHQxLCB0Miwgc3ViX3VwKSkgPT4KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBPayhTZWxmOjpub2RlX3RocmVlKHZhbCwgc3ViX3VwLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgKmxlZnQsIHQxLCB0MikpLAogICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgfSwKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICAgICAgCiAgICAgICAgICAgIH0KICAgICAgICAgICAgVGhyZWUoc2l6ZSwgdmFsMSwgdmFsMiwgbGVmdCwgbWlkZGxlLCByaWdodCkgPT4gewogICAgICAgICAgICAgICAgaWYgeCA9PSB2YWwxIHx8IHggPT0gdmFsMiB7CiAgICAgICAgICAgICAgICAgICAgcmV0dXJuIE9rKFRocmVlKHNpemUsIHZhbDEsIHZhbDIsIGxlZnQsIG1pZGRsZSwgcmlnaHQpKTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIGlmIHggPCB2YWwxIHsKICAgICAgICAgICAgICAgICAgICBtYXRjaCBsZWZ0Lmluc2VydF9zdWIoeCkgewogICAgICAgICAgICAgICAgICAgICAgICBPayhzdWJfdHIpID0+CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBPayhTZWxmOjpub2RlX3RocmVlKHZhbDEsIHZhbDIsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHN1Yl90ciwgKm1pZGRsZSwgKnJpZ2h0KSksCiAgICAgICAgICAgICAgICAgICAgICAgIEVycigodDEsIHQyLCBzdWJfdXApKSA9PiB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBsZXQgKHQxLCB0MiwgdikgPSBTZWxmOjpkaXZpZGVfZm91cigKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB0MSwgc3ViX3VwLCB0MiwgdmFsMSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAqbWlkZGxlLCB2YWwyLCAqcmlnaHQpOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgRXJyKCh0MSwgdDIsIHYpKQogICAgICAgICAgICAgICAgICAgICAgICB9LAogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIH0gZWxzZSBpZiB4IDwgdmFsMiB7CiAgICAgICAgICAgICAgICAgICAgbWF0Y2ggbWlkZGxlLmluc2VydF9zdWIoeCkgewogICAgICAgICAgICAgICAgICAgICAgICBPayhzdWJfdHIpID0+CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBPayhTZWxmOjpub2RlX3RocmVlKHZhbDEsIHZhbDIsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICpsZWZ0LCBzdWJfdHIsICpyaWdodCkpLAogICAgICAgICAgICAgICAgICAgICAgICBFcnIoKHQxLCB0Miwgc3ViX3VwKSkgPT4gewogICAgICAgICAgICAgICAgICAgICAgICAgICAgbGV0ICh0MSwgdDIsIHYpID0gU2VsZjo6ZGl2aWRlX2ZvdXIoCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgKmxlZnQsIHZhbDEsIHQxLCBzdWJfdXAsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgdDIsIHZhbDIsICpyaWdodCk7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBFcnIoKHQxLCB0MiwgdikpCiAgICAgICAgICAgICAgICAgICAgICAgIH0sCiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgICAgICAgICBtYXRjaCByaWdodC5pbnNlcnRfc3ViKHgpIHsKICAgICAgICAgICAgICAgICAgICAgICAgT2soc3ViX3RyKSA9PgogICAgICAgICAgICAgICAgICAgICAgICAgICAgT2soU2VsZjo6bm9kZV90aHJlZSh2YWwxLCB2YWwyLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAqbGVmdCwgKm1pZGRsZSwgc3ViX3RyKSksCiAgICAgICAgICAgICAgICAgICAgICAgIEVycigodDEsIHQyLCBzdWJfdXApKSA9PiB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBsZXQgKHQxLCB0MiwgdikgPSBTZWxmOjpkaXZpZGVfZm91cigKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAqbGVmdCwgdmFsMSwgKm1pZGRsZSwgdmFsMiwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB0MSwgc3ViX3VwLCB0Mik7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBFcnIoKHQxLCB0MiwgdikpCiAgICAgICAgICAgICAgICAgICAgICAgIH0sCiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQogICAgZm4gaW5zZXJ0KHNlbGYsIHg6IFQpIC0+IFNlbGYgewogICAgICAgIG1hdGNoIHNlbGYuaW5zZXJ0X3N1Yih4KSB7CiAgICAgICAgICAgIE9rKHQpID0+IHQsCiAgICAgICAgICAgIEVycigodDEsIHQyLCB2KSkgPT4KICAgICAgICAgICAgICAgIFNlbGY6Om5vZGVfdHdvKHYsIHQxLCB0MiksCiAgICAgICAgfQogICAgfQogICAgZm4gaW50b192ZWNfc3ViKHNlbGYsIHJldDogJm11dCBWZWM8VD4pIHsKICAgICAgICB1c2UgVHdvVGhyZWVUcmVlOjoqOwogICAgICAgIG1hdGNoIHNlbGYgewogICAgICAgICAgICBUaXAgPT4gKCksCiAgICAgICAgICAgIFR3byhfLCB2YWwsIGxlZnQsIHJpZ2h0KSA9PiB7CiAgICAgICAgICAgICAgICBsZWZ0LmludG9fdmVjX3N1YihyZXQpOwogICAgICAgICAgICAgICAgcmV0LnB1c2godmFsKTsKICAgICAgICAgICAgICAgIHJpZ2h0LmludG9fdmVjX3N1YihyZXQpOwogICAgICAgICAgICB9LAogICAgICAgICAgICBUaHJlZShfLCB2YWwxLCB2YWwyLCBsZWZ0LCBtaWRkbGUsIHJpZ2h0KSA9PiB7CiAgICAgICAgICAgICAgICBsZWZ0LmludG9fdmVjX3N1YihyZXQpOwogICAgICAgICAgICAgICAgcmV0LnB1c2godmFsMSk7CiAgICAgICAgICAgICAgICBtaWRkbGUuaW50b192ZWNfc3ViKHJldCk7CiAgICAgICAgICAgICAgICByZXQucHVzaCh2YWwyKTsKICAgICAgICAgICAgICAgIHJpZ2h0LmludG9fdmVjX3N1YihyZXQpOwogICAgICAgICAgICB9LAogICAgICAgIH0KICAgIH0KICAgIHB1YiBmbiBmaW5kX2luZGV4KCZzZWxmLCB4OiAmVCkgLT4gKHVzaXplLCBib29sKSB7CiAgICAgICAgdXNlIFR3b1RocmVlVHJlZTo6KjsKICAgICAgICBtYXRjaCAqc2VsZiB7CiAgICAgICAgICAgIFRpcCA9PiAoMCwgZmFsc2UpLAogICAgICAgICAgICBUd28oX3NpemUsIHJlZiB2LCByZWYgbGVmdCwgcmVmIHJpZ2h0KSA9PiB7CiAgICAgICAgICAgICAgICBtYXRjaCB4LmNtcCh2KSB7CiAgICAgICAgICAgICAgICAgICAgc3RkOjpjbXA6Ok9yZGVyaW5nOjpFcXVhbCA9PiAobGVmdC5zaXplKCksIHRydWUpLAogICAgICAgICAgICAgICAgICAgIHN0ZDo6Y21wOjpPcmRlcmluZzo6TGVzcyA9PiBsZWZ0LmZpbmRfaW5kZXgoeCksCiAgICAgICAgICAgICAgICAgICAgc3RkOjpjbXA6Ok9yZGVyaW5nOjpHcmVhdGVyID0+IHsKICAgICAgICAgICAgICAgICAgICAgICAgbGV0IChyZXMsIGZvdW5kKSA9IHJpZ2h0LmZpbmRfaW5kZXgoeCk7CiAgICAgICAgICAgICAgICAgICAgICAgIChyZXMgKyBsZWZ0LnNpemUoKSArIDEsIGZvdW5kKQogICAgICAgICAgICAgICAgICAgIH0sCiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0sCiAgICAgICAgICAgIFRocmVlKF9zaXplLCByZWYgdjEsIHJlZiB2MiwgcmVmIGxlZnQsIHJlZiBtaWRkbGUsIHJlZiByaWdodCkgPT4gewogICAgICAgICAgICAgICAgaWYgeCA9PSB2MSB7CiAgICAgICAgICAgICAgICAgICAgcmV0dXJuIChsZWZ0LnNpemUoKSwgdHJ1ZSk7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBpZiB4ID09IHYyIHsKICAgICAgICAgICAgICAgICAgICByZXR1cm4gKGxlZnQuc2l6ZSgpICsgbWlkZGxlLnNpemUoKSArIDEsIHRydWUpOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgaWYgeCA8IHYxIHsKICAgICAgICAgICAgICAgICAgICByZXR1cm4gbGVmdC5maW5kX2luZGV4KHgpOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgaWYgeCA8IHYyIHsKICAgICAgICAgICAgICAgICAgICBsZXQgKHJlcywgZm91bmQpID0gbWlkZGxlLmZpbmRfaW5kZXgoeCk7CiAgICAgICAgICAgICAgICAgICAgcmV0dXJuIChsZWZ0LnNpemUoKSArIDEgKyByZXMsIGZvdW5kKTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIGxldCAocmVzLCBmb3VuZCkgPSByaWdodC5maW5kX2luZGV4KHgpOwogICAgICAgICAgICAgICAgcmV0dXJuIChsZWZ0LnNpemUoKSArIG1pZGRsZS5zaXplKCkgKyAyICsgcmVzLCBmb3VuZCk7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CiAgICBwdWIgZm4gaW50b192ZWMoc2VsZikgLT4gVmVjPFQ+IHsKICAgICAgICBsZXQgbXV0IHJldCA9IFZlYzo6d2l0aF9jYXBhY2l0eShzZWxmLnNpemUoKSk7CiAgICAgICAgc2VsZi5pbnRvX3ZlY19zdWIoJm11dCByZXQpOwogICAgICAgIHJldAogICAgfQp9CgpmbiBkZXB0aDxUPih0OiAmVHdvVGhyZWVUcmVlPFQ+KSAtPiB1c2l6ZSB7CiAgICB1c2UgVHdvVGhyZWVUcmVlOjoqOwogICAgbWF0Y2ggKnQgewogICAgICAgIFRpcCA9PiAwLAogICAgICAgIFR3byhfLCBfLCByZWYgbGVmdCwgXykgPT4gMSArIGRlcHRoKGxlZnQpLAogICAgICAgIFRocmVlKF8sIF8sIF8sIHJlZiBsZWZ0LCBfLCBfKSA9PiAxICsgZGVwdGgobGVmdCksCiAgICB9Cn0KCmZuIG1haW4oKSB7CiAgICBsZXQgbXV0IGJzdCA9IFR3b1RocmVlVHJlZTo6bmV3KCk7CiAgICBsZXQgbXV0IHNlZWQ6IGk2NCA9IDB4ZGVhZGMwZGU7CiAgICBsZXQgbXV0IG5leHQgPSB8fCB7CiAgICAgICAgc2VlZCA9IHNlZWQud3JhcHBpbmdfbXVsKDB4MTIzNDU2NzhkZWFkYzBkMSkud3JhcHBpbmdfYWRkKDB4MTU1MSk7CiAgICAgICAgc2VlZAogICAgfTsKICAgIGNvbnN0IE46IHVzaXplID0gMTAwMDAwMDsKICAgIGZvciBfIGluIDAgLi4gMTAwMCB7IG5leHQoKTsgfQogICAgbGV0IG11dCBjdXJfZGVwdGggPSAwOwogICAgZm9yIGkgaW4gMCAuLiBOIHsKICAgICAgICBsZXQgZWxlbSA9IChuZXh0KCkgJiAweGZmZmZfZmZmZikgYXMgdXNpemU7CiAgICAgICAgYnN0ID0gYnN0Lmluc2VydChlbGVtKTsKICAgICAgICBsZXQgZGVwID0gZGVwdGgoJmJzdCk7CiAgICAgICAgaWYgY3VyX2RlcHRoICE9IGRlcCB7CiAgICAgICAgICAgIHByaW50bG4hKCJpID0ge30sIGRlcHRoID0ge30iLCBpLCBkZXApOwogICAgICAgICAgICBjdXJfZGVwdGggPSBkZXA7CiAgICAgICAgfQogICAgfQp9Cg==