/// Treap (balanced binary search tree)
/// Reference: https://w...content-available-to-author-only...e.net/iwiwi/2-12188757
/// Verified by: ARC061-D (http://a...content-available-to-author-only...r.jp/submissions/1172709)
/// 2150ms for n = 9*10^5, maybe a bit slow for an O(n * log(n))-time algorithm...
#[derive(Clone, Debug)]
enum Treap<T> {
Bin(
usize, // size
i64, // priority
T, // value
Box<Treap<T>>, // left
Box<Treap<T>>, // right
),
Tip,
}
impl<T: Ord> Treap<T> {
pub fn new() -> Self { Treap::Tip }
pub fn singleton(v: T, pri: i64) -> Self {
use Treap::*;
Bin(1, pri, v, Box::new(Tip), Box::new(Tip))
}
pub fn size(&self) -> usize {
use Treap::*;
match *self {
Tip => 0,
Bin(t, _, _, _, _) => t,
}
}
// Merges two BST. Their ownership is taken.
pub fn merge(left: Self, right: Self) -> Self {
use Treap::*;
match (left, right) {
(Tip, Tip) => Tip,
(Tip, x) => x,
(x, Tip) => x,
(Bin(lsize, lpri, lelem, lleft, lright),
Bin(rsize, rpri, relem, rleft, rright)) => {
if lpri > rpri {
let right = Bin(rsize, rpri, relem, rleft, rright);
let mut ret = Bin(lsize, lpri, lelem, lleft,
Box::new(Self::merge(*lright, right)));
ret.update();
ret
} else {
let left = Bin(lsize, lpri, lelem, lleft, lright);
let mut ret = Bin(rsize, rpri, relem,
Box::new(Self::merge(left, *rleft)),
rright);
ret.update();
ret
}
}
}
}
pub fn split(self, k: usize) -> (Self, Self) {
use Treap::*;
match self {
Tip => (Tip, Tip),
Bin(size, pri, elem, left, right) => {
if k <= left.size() {
let (sl, sr) = Self::split(*left, k);
let mut ret = Bin(size, pri, elem, Box::new(sr), right);
ret.update();
(sl, ret)
} else {
let (sl, sr) = Self::split(*right, k - left.size() - 1);
let mut ret = Bin(size, pri, elem, left, Box::new(sl));
ret.update();
(ret, sr)
}
}
}
}
fn update(&mut self) {
use Treap::*;
match *self {
Tip => (),
Bin(ref mut lsize, ref _pri, ref _elem, ref left, ref right) => {
*lsize = left.size() + right.size() + 1;
},
}
}
fn insert_at(self, v: T, pri: i64, k: usize) -> Self {
use Treap::*;
// Speed up: compare the priority
match self {
Tip => Self::singleton(v, pri),
Bin(size, spri, elem, left, right) => {
let lsize = left.size();
if spri <= pri {
let cself = Bin(size, spri, elem, left, right);
let (left, right) = cself.split(k);
return Bin(size + 1, pri, v,
Box::new(left), Box::new(right));
}
if k < lsize {
return Bin(size + 1, spri, elem,
Box::new((*left).insert_at(v, pri, k)),
right);
}
if k >= lsize + 1 {
return Bin(size + 1, spri, elem,
left,
Box::new((*right)
.insert_at(v, pri, k - lsize - 1)));
}
let cself = Bin(size, spri, elem, left, right);
let sing = Self::singleton(v, pri);
let (left, right) = cself.split(k);
let tmp = Self::merge(left, sing);
Self::merge(tmp, right)
}
}
}
fn erase_at(self, k: usize) -> Self {
use Treap::*;
match self {
Tip => Tip,
Bin(size, pri, elem, left, right) => {
if k < left.size() {
return Bin(size - 1, pri, elem,
Box::new((*left).erase_at(k)), right);
}
if k == left.size() {
return Self::merge(*left, *right); // hit
}
let lsize = left.size();
return Bin(size - 1, pri, elem,
left,
Box::new((*right).erase_at(k - lsize - 1)));
}
}
}
fn find_index(&self, t: &T) -> (usize, bool) {
use Treap::*;
use std::cmp::Ordering;
let mut offset = 0;
let mut tap = self;
loop {
match *tap {
Tip => return (offset, false),
Bin(_, _, ref elem, ref left, ref right) => {
match elem.cmp(t) {
Ordering::Equal => return (offset + left.size(), true),
Ordering::Greater =>
tap = left,
Ordering::Less => {
offset += left.size() + 1;
tap = right;
},
}
}
}
}
}
#[allow(dead_code)]
fn insert(self, v: T, pri: i64) -> Self {
let (idx, found) = self.find_index(&v);
if found {
self
} else {
self.insert_at(v, pri, idx)
}
}
#[allow(dead_code)]
fn erase(self, v: &T) -> Self {
let (idx, found) = self.find_index(v);
if found {
self.erase_at(idx)
} else {
self
}
}
fn into_vec_sub(self, vec: &mut Vec<T>) {
use Treap::*;
match self {
Tip => (),
Bin(_, _, elem, left, right) => {
left.into_vec_sub(vec);
vec.push(elem);
right.into_vec_sub(vec);
}
}
}
#[allow(dead_code)]
pub fn into_vec(self) -> Vec<T> {
let mut ret = Vec::new();
self.into_vec_sub(&mut ret);
ret
}
}
fn depth<T>(t: &Treap<T>) -> usize {
match *t {
Treap::Tip => 0,
Treap::Bin(_, _, _, ref left, ref right) => {
std::cmp::max(depth(left), depth(right)) + 1
}
}
}
fn main() {
let mut bst = Treap::Tip::<usize>;
let mut seed: i64 = 0xdeadc0de;
let mut next = || {
seed = seed.wrapping_mul(0x12345678deadc0d1).wrapping_add(0x1551);
seed
};
const N: usize = 30000;
for _ in 0 .. 1000 { next(); }
let mut cur_depth = 0;
for i in 0 .. N {
bst = bst.insert(i, next());
let dep = depth(&bst);
if cur_depth != dep {
println!("i = {}, depth = {}", i, dep);
cur_depth = dep;
}
}
}
Ly8vIFRyZWFwIChiYWxhbmNlZCBiaW5hcnkgc2VhcmNoIHRyZWUpCi8vLyBSZWZlcmVuY2U6IGh0dHBzOi8vdy4uLmNvbnRlbnQtYXZhaWxhYmxlLXRvLWF1dGhvci1vbmx5Li4uZS5uZXQvaXdpd2kvMi0xMjE4ODc1NwovLy8gVmVyaWZpZWQgYnk6IEFSQzA2MS1EIChodHRwOi8vYS4uLmNvbnRlbnQtYXZhaWxhYmxlLXRvLWF1dGhvci1vbmx5Li4uci5qcC9zdWJtaXNzaW9ucy8xMTcyNzA5KQovLy8gMjE1MG1zIGZvciBuID0gOSoxMF41LCBtYXliZSBhIGJpdCBzbG93IGZvciBhbiBPKG4gKiBsb2cobikpLXRpbWUgYWxnb3JpdGhtLi4uCiNbZGVyaXZlKENsb25lLCBEZWJ1ZyldCmVudW0gVHJlYXA8VD4gewogICAgQmluKAogICAgICAgIHVzaXplLCAvLyBzaXplCiAgICAgICAgaTY0LCAvLyBwcmlvcml0eQogICAgICAgIFQsIC8vIHZhbHVlCiAgICAgICAgQm94PFRyZWFwPFQ+PiwgLy8gbGVmdAogICAgICAgIEJveDxUcmVhcDxUPj4sIC8vIHJpZ2h0CiAgICApLAogICAgVGlwLAp9CgppbXBsPFQ6IE9yZD4gVHJlYXA8VD4gewogICAgcHViIGZuIG5ldygpIC0+IFNlbGYgeyBUcmVhcDo6VGlwIH0KICAgIHB1YiBmbiBzaW5nbGV0b24odjogVCwgcHJpOiBpNjQpIC0+IFNlbGYgewogICAgICAgIHVzZSBUcmVhcDo6KjsKICAgICAgICBCaW4oMSwgcHJpLCB2LCBCb3g6Om5ldyhUaXApLCBCb3g6Om5ldyhUaXApKQogICAgfQogICAgcHViIGZuIHNpemUoJnNlbGYpIC0+IHVzaXplIHsKICAgICAgICB1c2UgVHJlYXA6Oio7CiAgICAgICAgbWF0Y2ggKnNlbGYgewogICAgICAgICAgICBUaXAgPT4gMCwKICAgICAgICAgICAgQmluKHQsIF8sICBfLCBfLCBfKSA9PiB0LAogICAgICAgIH0KICAgIH0KICAgIC8vIE1lcmdlcyB0d28gQlNULiBUaGVpciBvd25lcnNoaXAgaXMgdGFrZW4uCiAgICBwdWIgZm4gbWVyZ2UobGVmdDogU2VsZiwgcmlnaHQ6IFNlbGYpIC0+IFNlbGYgewogICAgICAgIHVzZSBUcmVhcDo6KjsKICAgICAgICBtYXRjaCAobGVmdCwgcmlnaHQpIHsKICAgICAgICAgICAgKFRpcCwgVGlwKSA9PiBUaXAsCiAgICAgICAgICAgIChUaXAsIHgpID0+IHgsCiAgICAgICAgICAgICh4LCBUaXApID0+IHgsCiAgICAgICAgICAgIChCaW4obHNpemUsIGxwcmksIGxlbGVtLCBsbGVmdCwgbHJpZ2h0KSwKICAgICAgICAgICAgIEJpbihyc2l6ZSwgcnByaSwgcmVsZW0sIHJsZWZ0LCBycmlnaHQpKSA9PiB7CiAgICAgICAgICAgICAgICBpZiBscHJpID4gcnByaSB7CiAgICAgICAgICAgICAgICAgICAgbGV0IHJpZ2h0ID0gQmluKHJzaXplLCBycHJpLCByZWxlbSwgcmxlZnQsIHJyaWdodCk7CiAgICAgICAgICAgICAgICAgICAgbGV0IG11dCByZXQgPSBCaW4obHNpemUsIGxwcmksIGxlbGVtLCBsbGVmdCwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIEJveDo6bmV3KFNlbGY6Om1lcmdlKCpscmlnaHQsIHJpZ2h0KSkpOwogICAgICAgICAgICAgICAgICAgIHJldC51cGRhdGUoKTsKICAgICAgICAgICAgICAgICAgICByZXQKICAgICAgICAgICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgICAgICAgICAgbGV0IGxlZnQgPSBCaW4obHNpemUsIGxwcmksIGxlbGVtLCBsbGVmdCwgbHJpZ2h0KTsKICAgICAgICAgICAgICAgICAgICBsZXQgbXV0IHJldCA9IEJpbihyc2l6ZSwgcnByaSwgcmVsZW0sCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgQm94OjpuZXcoU2VsZjo6bWVyZ2UobGVmdCwgKnJsZWZ0KSksCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcnJpZ2h0KTsKICAgICAgICAgICAgICAgICAgICByZXQudXBkYXRlKCk7CiAgICAgICAgICAgICAgICAgICAgcmV0CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CiAgICBwdWIgZm4gc3BsaXQoc2VsZiwgazogdXNpemUpIC0+IChTZWxmLCBTZWxmKSB7CiAgICAgICAgdXNlIFRyZWFwOjoqOwogICAgICAgIG1hdGNoIHNlbGYgewogICAgICAgICAgICBUaXAgPT4gKFRpcCwgVGlwKSwKICAgICAgICAgICAgQmluKHNpemUsIHByaSwgZWxlbSwgbGVmdCwgcmlnaHQpID0+IHsKICAgICAgICAgICAgICAgIGlmIGsgPD0gbGVmdC5zaXplKCkgewogICAgICAgICAgICAgICAgICAgIGxldCAoc2wsIHNyKSA9IFNlbGY6OnNwbGl0KCpsZWZ0LCBrKTsKICAgICAgICAgICAgICAgICAgICBsZXQgbXV0IHJldCA9IEJpbihzaXplLCBwcmksIGVsZW0sIEJveDo6bmV3KHNyKSwgcmlnaHQpOwogICAgICAgICAgICAgICAgICAgIHJldC51cGRhdGUoKTsKICAgICAgICAgICAgICAgICAgICAoc2wsIHJldCkKICAgICAgICAgICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgICAgICAgICAgbGV0IChzbCwgc3IpID0gU2VsZjo6c3BsaXQoKnJpZ2h0LCBrIC0gbGVmdC5zaXplKCkgLSAxKTsKICAgICAgICAgICAgICAgICAgICBsZXQgbXV0IHJldCA9IEJpbihzaXplLCBwcmksIGVsZW0sIGxlZnQsIEJveDo6bmV3KHNsKSk7CiAgICAgICAgICAgICAgICAgICAgcmV0LnVwZGF0ZSgpOwogICAgICAgICAgICAgICAgICAgIChyZXQsIHNyKQogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQogICAgZm4gdXBkYXRlKCZtdXQgc2VsZikgewogICAgICAgIHVzZSBUcmVhcDo6KjsKICAgICAgICBtYXRjaCAqc2VsZiB7CiAgICAgICAgICAgIFRpcCA9PiAoKSwKICAgICAgICAgICAgQmluKHJlZiBtdXQgbHNpemUsIHJlZiBfcHJpLCByZWYgX2VsZW0sIHJlZiBsZWZ0LCByZWYgcmlnaHQpID0+IHsKICAgICAgICAgICAgICAgICpsc2l6ZSA9IGxlZnQuc2l6ZSgpICsgcmlnaHQuc2l6ZSgpICsgMTsKICAgICAgICAgICAgfSwKICAgICAgICB9CiAgICB9CiAgICBmbiBpbnNlcnRfYXQoc2VsZiwgdjogVCwgcHJpOiBpNjQsIGs6IHVzaXplKSAtPiBTZWxmIHsKICAgICAgICB1c2UgVHJlYXA6Oio7CiAgICAgICAgLy8gU3BlZWQgdXA6IGNvbXBhcmUgdGhlIHByaW9yaXR5CiAgICAgICAgbWF0Y2ggc2VsZiB7CiAgICAgICAgICAgIFRpcCA9PiBTZWxmOjpzaW5nbGV0b24odiwgcHJpKSwKICAgICAgICAgICAgQmluKHNpemUsIHNwcmksIGVsZW0sIGxlZnQsIHJpZ2h0KSA9PiB7CiAgICAgICAgICAgICAgICBsZXQgbHNpemUgPSBsZWZ0LnNpemUoKTsKICAgICAgICAgICAgICAgIGlmIHNwcmkgPD0gcHJpIHsKICAgICAgICAgICAgICAgICAgICBsZXQgY3NlbGYgPSBCaW4oc2l6ZSwgc3ByaSwgZWxlbSwgbGVmdCwgcmlnaHQpOwogICAgICAgICAgICAgICAgICAgIGxldCAobGVmdCwgcmlnaHQpID0gY3NlbGYuc3BsaXQoayk7CiAgICAgICAgICAgICAgICAgICAgcmV0dXJuIEJpbihzaXplICsgMSwgcHJpLCB2LAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgQm94OjpuZXcobGVmdCksIEJveDo6bmV3KHJpZ2h0KSk7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBpZiBrIDwgbHNpemUgewogICAgICAgICAgICAgICAgICAgIHJldHVybiBCaW4oc2l6ZSArIDEsIHNwcmksIGVsZW0sCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBCb3g6Om5ldygoKmxlZnQpLmluc2VydF9hdCh2LCBwcmksIGspKSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHJpZ2h0KTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIGlmIGsgPj0gbHNpemUgKyAxIHsKICAgICAgICAgICAgICAgICAgICByZXR1cm4gQmluKHNpemUgKyAxLCBzcHJpLCBlbGVtLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgbGVmdCwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIEJveDo6bmV3KCgqcmlnaHQpCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAuaW5zZXJ0X2F0KHYsIHByaSwgayAtIGxzaXplIC0gMSkpKTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIGxldCBjc2VsZiA9IEJpbihzaXplLCBzcHJpLCBlbGVtLCBsZWZ0LCByaWdodCk7CiAgICAgICAgICAgICAgICBsZXQgc2luZyA9IFNlbGY6OnNpbmdsZXRvbih2LCBwcmkpOwogICAgICAgICAgICAgICAgbGV0IChsZWZ0LCByaWdodCkgPSBjc2VsZi5zcGxpdChrKTsKICAgICAgICAgICAgICAgIGxldCB0bXAgPSBTZWxmOjptZXJnZShsZWZ0LCBzaW5nKTsKICAgICAgICAgICAgICAgIFNlbGY6Om1lcmdlKHRtcCwgcmlnaHQpCiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CiAgICBmbiBlcmFzZV9hdChzZWxmLCBrOiB1c2l6ZSkgLT4gU2VsZiB7CiAgICAgICAgdXNlIFRyZWFwOjoqOwogICAgICAgIG1hdGNoIHNlbGYgewogICAgICAgICAgICBUaXAgPT4gVGlwLAogICAgICAgICAgICBCaW4oc2l6ZSwgcHJpLCBlbGVtLCBsZWZ0LCByaWdodCkgPT4gewogICAgICAgICAgICAgICAgaWYgayA8IGxlZnQuc2l6ZSgpIHsKICAgICAgICAgICAgICAgICAgICByZXR1cm4gQmluKHNpemUgLSAxLCBwcmksIGVsZW0sCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBCb3g6Om5ldygoKmxlZnQpLmVyYXNlX2F0KGspKSwgcmlnaHQpOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgaWYgayA9PSBsZWZ0LnNpemUoKSB7CiAgICAgICAgICAgICAgICAgICAgcmV0dXJuIFNlbGY6Om1lcmdlKCpsZWZ0LCAqcmlnaHQpOyAvLyBoaXQKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIGxldCBsc2l6ZSA9IGxlZnQuc2l6ZSgpOwogICAgICAgICAgICAgICAgcmV0dXJuIEJpbihzaXplIC0gMSwgcHJpLCBlbGVtLAogICAgICAgICAgICAgICAgICAgICAgICAgICBsZWZ0LAogICAgICAgICAgICAgICAgICAgICAgICAgICBCb3g6Om5ldygoKnJpZ2h0KS5lcmFzZV9hdChrIC0gbHNpemUgLSAxKSkpOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQogICAgZm4gZmluZF9pbmRleCgmc2VsZiwgdDogJlQpIC0+ICh1c2l6ZSwgYm9vbCkgewogICAgICAgIHVzZSBUcmVhcDo6KjsKICAgICAgICB1c2Ugc3RkOjpjbXA6Ok9yZGVyaW5nOwogICAgICAgIGxldCBtdXQgb2Zmc2V0ID0gMDsKICAgICAgICBsZXQgbXV0IHRhcCA9IHNlbGY7CiAgICAgICAgbG9vcCB7CiAgICAgICAgICAgIG1hdGNoICp0YXAgewogICAgICAgICAgICAgICAgVGlwID0+IHJldHVybiAob2Zmc2V0LCBmYWxzZSksCiAgICAgICAgICAgICAgICBCaW4oXywgXywgcmVmIGVsZW0sIHJlZiBsZWZ0LCByZWYgcmlnaHQpID0+IHsKICAgICAgICAgICAgICAgICAgICBtYXRjaCBlbGVtLmNtcCh0KSB7CiAgICAgICAgICAgICAgICAgICAgICAgIE9yZGVyaW5nOjpFcXVhbCA9PiByZXR1cm4gKG9mZnNldCArIGxlZnQuc2l6ZSgpLCB0cnVlKSwKICAgICAgICAgICAgICAgICAgICAgICAgT3JkZXJpbmc6OkdyZWF0ZXIgPT4KICAgICAgICAgICAgICAgICAgICAgICAgICAgIHRhcCA9IGxlZnQsCiAgICAgICAgICAgICAgICAgICAgICAgIE9yZGVyaW5nOjpMZXNzID0+IHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIG9mZnNldCArPSBsZWZ0LnNpemUoKSArIDE7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICB0YXAgPSByaWdodDsKICAgICAgICAgICAgICAgICAgICAgICAgfSwKICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CiAgICAjW2FsbG93KGRlYWRfY29kZSldCiAgICBmbiBpbnNlcnQoc2VsZiwgdjogVCwgcHJpOiBpNjQpIC0+IFNlbGYgewogICAgICAgIGxldCAoaWR4LCBmb3VuZCkgPSBzZWxmLmZpbmRfaW5kZXgoJnYpOwogICAgICAgIGlmIGZvdW5kIHsKICAgICAgICAgICAgc2VsZgogICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgIHNlbGYuaW5zZXJ0X2F0KHYsIHByaSwgaWR4KQogICAgICAgIH0KICAgIH0KICAgICNbYWxsb3coZGVhZF9jb2RlKV0KICAgIGZuIGVyYXNlKHNlbGYsIHY6ICZUKSAtPiBTZWxmIHsKICAgICAgICBsZXQgKGlkeCwgZm91bmQpID0gc2VsZi5maW5kX2luZGV4KHYpOwogICAgICAgIGlmIGZvdW5kIHsKICAgICAgICAgICAgc2VsZi5lcmFzZV9hdChpZHgpCiAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgc2VsZgogICAgICAgIH0KICAgIH0KICAgIGZuIGludG9fdmVjX3N1YihzZWxmLCB2ZWM6ICZtdXQgVmVjPFQ+KSB7CiAgICAgICAgdXNlIFRyZWFwOjoqOwogICAgICAgIG1hdGNoIHNlbGYgewogICAgICAgICAgICBUaXAgPT4gKCksCiAgICAgICAgICAgIEJpbihfLCBfLCBlbGVtLCBsZWZ0LCByaWdodCkgPT4gewogICAgICAgICAgICAgICAgbGVmdC5pbnRvX3ZlY19zdWIodmVjKTsKICAgICAgICAgICAgICAgIHZlYy5wdXNoKGVsZW0pOwogICAgICAgICAgICAgICAgcmlnaHQuaW50b192ZWNfc3ViKHZlYyk7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CiAgICAjW2FsbG93KGRlYWRfY29kZSldCiAgICBwdWIgZm4gaW50b192ZWMoc2VsZikgLT4gVmVjPFQ+IHsKICAgICAgICBsZXQgbXV0IHJldCA9IFZlYzo6bmV3KCk7CiAgICAgICAgc2VsZi5pbnRvX3ZlY19zdWIoJm11dCByZXQpOwogICAgICAgIHJldAogICAgfQp9CgpmbiBkZXB0aDxUPih0OiAmVHJlYXA8VD4pIC0+IHVzaXplIHsKICAgIG1hdGNoICp0IHsKICAgICAgICBUcmVhcDo6VGlwID0+IDAsCiAgICAgICAgVHJlYXA6OkJpbihfLCBfLCBfLCByZWYgbGVmdCwgcmVmIHJpZ2h0KSA9PiB7CiAgICAgICAgICAgIHN0ZDo6Y21wOjptYXgoZGVwdGgobGVmdCksIGRlcHRoKHJpZ2h0KSkgKyAxCiAgICAgICAgfQogICAgfQp9CgpmbiBtYWluKCkgewogICAgbGV0IG11dCBic3QgPSBUcmVhcDo6VGlwOjo8dXNpemU+OwogICAgbGV0IG11dCBzZWVkOiBpNjQgPSAweGRlYWRjMGRlOwogICAgbGV0IG11dCBuZXh0ID0gfHwgewogICAgICAgIHNlZWQgPSBzZWVkLndyYXBwaW5nX211bCgweDEyMzQ1Njc4ZGVhZGMwZDEpLndyYXBwaW5nX2FkZCgweDE1NTEpOwogICAgICAgIHNlZWQKICAgIH07CiAgICBjb25zdCBOOiB1c2l6ZSA9IDMwMDAwOwogICAgZm9yIF8gaW4gMCAuLiAxMDAwIHsgbmV4dCgpOyB9CiAgICBsZXQgbXV0IGN1cl9kZXB0aCA9IDA7CiAgICBmb3IgaSBpbiAwIC4uIE4gewogICAgICAgIGJzdCA9IGJzdC5pbnNlcnQoaSwgbmV4dCgpKTsKICAgICAgICBsZXQgZGVwID0gZGVwdGgoJmJzdCk7CiAgICAgICAgaWYgY3VyX2RlcHRoICE9IGRlcCB7CiAgICAgICAgICAgIHByaW50bG4hKCJpID0ge30sIGRlcHRoID0ge30iLCBpLCBkZXApOwogICAgICAgICAgICBjdXJfZGVwdGggPSBkZXA7CiAgICAgICAgfQogICAgfQp9Cg==