/* package codechef; // don't place package name! */
import java.util.* ;
import java.lang.* ;
import java.io.* ;
/* Name of the class has to be "Main" only if the class is public. */
class Main
{
static int intmax
= Integer .
MAX_VALUE ; static int intmin
= Integer .
MIN_VALUE ; static long mod = 1000000007L;
{
FastReader get = new FastReader( ) ;
int T = get.nextInt ( ) ;
while ( T--> 0 )
{
int m= get.nextInt ( ) , n= get.nextInt ( ) ;
int [ ] X = new int [ m- 1 ] ;
int [ ] Y = new int [ n- 1 ] ;
for ( int i= 0 ; i< m- 1 ; i++ ) X[ i] = get.nextInt ( ) ;
for ( int i= 0 ; i< n- 1 ; i++ ) Y[ i] = get.nextInt ( ) ;
ans( X, Y, m, n ) ;
put.flush ( ) ;
}
put.close ( ) ;
}
public static void ans
( int [ ] X,
int [ ] Y,
int m,
int n
) throws java.
lang .
Exception {
ArrayList< Pair> pp = new ArrayList<> ( ) ;
for ( int i= 0 ; i< X.length ; i++ ) pp.add ( new Pair( X[ i] , 1 ) ) ;
for ( int i= 0 ; i< Y.length ; i++ ) pp.add ( new Pair( Y[ i] , 2 ) ) ;
int v_cuts = 1 , h_cuts = 1 ;
long cost = 0 ;
for ( int i= 0 ; i< pp.size ( ) ; i++ )
{
Pair p = pp.get ( i) ;
if ( p.b == 2 )
{
cost += ( long ) p.a * v_cuts;
h_cuts++;
}
else
{
cost += ( long ) p.a * h_cuts;
v_cuts++;
}
}
put.write ( cost+ "\n " ) ;
}
//
// FUNCTIONS BELOW :
// isPrime(), lcm(), gcd(), totient(), findDiv(), sortInt(), sortLong(),
// power(), freqArr(), MATRIX: multiply(), power()
// CLASSES BELOW :
// DSU, FenwickTree, SegmentTree, LazySegTree, RangeBit, SparseTable, LCA, BitSet, MaxFlow
//
public static int [ ] readArr
( int N, FastReader get
) throws Exception {
int [ ] arr = new int [ N] ;
for ( int i
= 0 ; i
< N
; i
++ ) arr
[ i
] = Integer .
parseInt ( st.
nextToken ( ) ) ;
return arr;
}
public static long [ ] readArr2
( int N, FastReader get
) throws Exception {
long [ ] arr = new long [ N] ;
for ( int i
= 0 ; i
< N
; i
++ ) arr
[ i
] = Long .
parseLong ( st.
nextToken ( ) ) ;
return arr;
}
public static int [ ] [ ] readMat
( int N,
int M, FastReader get
) throws Exception {
int [ ] [ ] mat = new int [ N] [ M] ;
for ( int i= 0 ; i < N; i++ )
{
for ( int j
= 0 ; j
< M
; j
++ ) mat
[ i
] [ j
] = Integer .
parseInt ( st.
nextToken ( ) ) ; }
return mat;
}
public static void print
( int [ ] arr
) throws java.
lang .
Exception {
for ( int x: arr)
put.write ( x+ " " ) ;
put.write ( "\n " ) ;
}
public static void printMat
( int [ ] [ ] arr
) throws java.
lang .
Exception {
for ( int i= 0 ; i < arr.length ; i++ )
{
for ( int j= 0 ; j < arr[ 0 ] .length ; j++ )
{
put.write ( arr[ i] [ j] + " " ) ;
}
put.write ( "\n " ) ;
}
put.write ( "\n " ) ;
}
public static boolean isPrime( long n)
{
if ( n < 2 ) return false ;
if ( n == 2 || n == 3 ) return true ;
if ( n% 2 == 0 || n% 3 == 0 ) return false ;
long sqrtN
= ( long ) Math .
sqrt ( n
) + 1 ; for ( long i = 6L; i <= sqrtN; i += 6 ) {
if ( n% ( i- 1 ) == 0 || n% ( i+ 1 ) == 0 ) return false ;
}
return true ;
}
public static long lcm( long a, long b)
{
return ( a / gcd( a, b) ) * b;
}
public static long gcd( long a, long b)
{
if ( a > b) a = ( a+ b) - ( b= a) ;
if ( a == 0L) return b;
return gcd( b% a, a) ;
}
public static long totient( long n)
{
long result = n;
for ( int p = 2 ; p* p <= n; ++ p)
if ( n % p == 0 )
{
while ( n% p == 0 )
n /= p;
result -= result/ p;
}
if ( n > 1 ) result -= result/ n;
return result;
}
public static ArrayList< Integer> findDiv( int N)
{
//gets all divisors of N
ArrayList< Integer> ls1 = new ArrayList< Integer> ( ) ;
ArrayList< Integer> ls2 = new ArrayList< Integer> ( ) ;
for ( int i
= 1 ; i
<= ( int ) ( Math .
sqrt ( N
) + 0.00000001 ) ; i
++ ) if ( N% i == 0 )
{
ls1.add ( i) ;
ls2.add ( N/ i) ;
}
for ( int b: ls2)
if ( b != ls1.get ( ls1.size ( ) - 1 ) )
ls1.add ( b) ;
return ls1;
}
public static void sortInt( int [ ] arr)
{
//because Arrays.sort() uses quicksort which is dumb
//Collections.sort() uses merge sort
ArrayList< Integer> ls = new ArrayList< Integer> ( ) ;
for ( int x: arr) ls.add ( x) ;
for ( int i= 0 ; i < arr.length ; i++ ) arr[ i] = ls.get ( i) ;
}
public static void sortLong( long [ ] arr)
{
//because Arrays.sort() uses quicksort which is dumb
//Collections.sort() uses merge sort
ArrayList< Long> ls = new ArrayList< Long> ( ) ;
for ( long x: arr) ls.add ( x) ;
for ( int i= 0 ; i < arr.length ; i++ ) arr[ i] = ls.get ( i) ;
}
public static void sortChar( char [ ] arr)
{
//because Arrays.sort() uses quicksort which is dumb
//Collections.sort() uses merge sort
ArrayList< Character> ls = new ArrayList< Character> ( ) ;
for ( char x: arr) ls.add ( x) ;
for ( int i= 0 ; i < arr.length ; i++ ) arr[ i] = ls.get ( i) ;
}
{
char tempArray[ ] = inputString.toCharArray ( ) ;
sortChar( tempArray) ;
}
public static long power( long x, long y, long p)
{
//0^0 = 1
long res = 1L;
x = x% p;
while ( y > 0 )
{
if ( ( y& 1 ) == 1 )
res = ( res* x) % p;
y >>= 1 ;
x = ( x* x) % p;
}
return res;
}
//custom multiset (replace with HashMap if needed)
public static void push
( TreeMap
< Integer , Integer
> map,
int k,
int v
) {
//map[k] += v;
if ( ! map.containsKey ( k) ) map.put ( k, v) ;
else map.put ( k, map.get ( k) + v) ;
}
public static void pull
( TreeMap
< Integer , Integer
> map,
int k,
int v
) {
//assumes map[k] >= v
//map[k] -= v
int lol = map.get ( k) ;
if ( lol == v) map.remove ( k) ;
else map.put ( k, lol- v) ;
}
public static HashMap
< Integer , Integer
> freqMap
( int [ ] arr
) {
for ( int x: arr)
if ( ! map.containsKey ( x) ) map.put ( x, map.get ( x) + 1 ) ;
else map.put ( x, 1 ) ;
return map;
}
public static long [ ] [ ] multiply( long [ ] [ ] left, long [ ] [ ] right)
{
long MOD = 1000000007L;
int N = left.length ;
int M = right[ 0 ] .length ;
long [ ] [ ] res = new long [ N] [ M] ;
for ( int a= 0 ; a < N; a++ )
for ( int b= 0 ; b < M; b++ )
for ( int c= 0 ; c < left[ 0 ] .length ; c++ )
{
res[ a] [ b] += ( left[ a] [ c] * right[ c] [ b] ) % MOD;
if ( res[ a] [ b] >= MOD)
res[ a] [ b] -= MOD;
}
return res;
}
public static long [ ] [ ] power( long [ ] [ ] grid, long pow)
{
long [ ] [ ] res = new long [ grid.length ] [ grid[ 0 ] .length ] ;
for ( int i= 0 ; i < res.length ; i++ )
res[ i] [ i] = 1L;
long [ ] [ ] curr = grid.clone ( ) ;
while ( pow > 0 )
{
if ( ( pow& 1L) == 1L)
res = multiply( curr, res) ;
pow >>= 1 ;
curr = multiply( curr, curr) ;
}
return res;
}
}
class Pair implements Comparable< Pair>
{
int a, b;
public Pair( int a, int b)
{
this .a = a;
this .b = b;
}
@Override
public int compareTo( Pair p)
{
if ( this .a > p.a ) return - 1 ;
else if ( this .a < p.a ) return 1 ;
else
{
if ( this .b > p.b ) return - 1 ;
else return 1 ;
}
}
}
class DSU
{
public int [ ] dsu;
public int [ ] size;
public DSU( int N)
{
dsu = new int [ N+ 1 ] ;
size = new int [ N+ 1 ] ;
for ( int i= 0 ; i <= N; i++ )
{
dsu[ i] = i;
size[ i] = 1 ;
}
}
//with path compression, no find by rank
public int find( int x)
{
return dsu[ x] == x ? x : ( dsu[ x] = find( dsu[ x] ) ) ;
}
public void merge( int x, int y)
{
int fx = find( x) ;
int fy = find( y) ;
dsu[ fx] = fy;
}
public void merge( int x, int y, boolean sized)
{
int fx = find( x) ;
int fy = find( y) ;
size[ fy] += size[ fx] ;
dsu[ fx] = fy;
}
}
class FenwickTree
{
//Binary Indexed Tree
//1 indexed
public int [ ] tree;
public int size;
public FenwickTree( int size)
{
this .size = size;
tree = new int [ size+ 5 ] ;
}
public void add( int i, int v)
{
while ( i <= size)
{
tree[ i] += v;
i += i&- i;
}
}
public int find( int i)
{
int res = 0 ;
while ( i >= 1 )
{
res += tree[ i] ;
i -= i&- i;
}
return res;
}
public int find( int l, int r)
{
return find( r) - find( l- 1 ) ;
}
}
class SegmentTree
{
//Tlatoani's segment tree
//iterative implementation = low constant runtime factor
//range query, non lazy
final int [ ] val;
final int treeFrom;
final int length;
public SegmentTree( int treeFrom, int treeTo)
{
this .treeFrom = treeFrom;
int length = treeTo - treeFrom + 1 ;
int l;
for ( l = 0 ; ( 1 << l) < length; l++ ) ;
val = new int [ 1 << ( l + 1 ) ] ;
this .length = 1 << l;
}
public void update( int index, int delta)
{
//replaces value
int node = index - treeFrom + length;
val[ node] = delta;
for ( node >>= 1 ; node > 0 ; node >>= 1 )
val[ node] = comb( val[ node << 1 ] , val[ ( node << 1 ) + 1 ] ) ;
}
public int query( int from, int to)
{
//inclusive bounds
if ( to < from)
return 0 ; //0 or 1?
from += length - treeFrom;
to += length - treeFrom + 1 ;
//0 or 1?
int res = 0 ;
for ( ; from + ( from & - from) <= to; from += from & - from)
res = comb( res, val[ from / ( from & - from) ] ) ;
for ( ; to - ( to & - to) >= from; to -= to & - to)
res = comb( res, val[ ( to - ( to & - to) ) / ( to & - to) ] ) ;
return res;
}
public int comb( int a, int b)
{
//change this
}
}
class LazySegTree
{
//definitions
private int NULL = - 1 ;
private int [ ] tree;
private int [ ] lazy;
private int length;
public LazySegTree( int N)
{
length = N; int b;
for ( b= 0 ; ( 1 << b) < length; b++ ) ;
tree = new int [ 1 << ( b+ 1 ) ] ;
lazy = new int [ 1 << ( b+ 1 ) ] ;
}
public int query( int left, int right)
{
//left and right are 0-indexed
return get( 1 , 0 , length- 1 , left, right) ;
}
private int get( int v, int currL, int currR, int L, int R)
{
if ( L > R)
return NULL ;
if ( L <= currL && currR <= R)
return tree[ v] ;
propagate( v) ;
int mid = ( currL+ currR) / 2 ;
return comb
( get
( v
* 2 , currL, mid, L,
Math .
min ( R, mid
) ) ,
get
( v
* 2 + 1 , mid
+ 1 , currR,
Math .
max ( L, mid
+ 1 ) , R
) ) ; }
public void update( int left, int right, int delta)
{
add( 1 , 0 , length- 1 , left, right, delta) ;
}
private void add( int v, int currL, int currR, int L, int R, int delta)
{
if ( L > R)
return ;
if ( currL == L && currR == R)
{
//exact covering
tree[ v] += delta;
lazy[ v] += delta;
return ;
}
propagate( v) ;
int mid = ( currL+ currR) / 2 ;
add
( v
* 2 , currL, mid, L,
Math .
min ( R, mid
) , delta
) ; add
( v
* 2 + 1 , mid
+ 1 , currR,
Math .
max ( L, mid
+ 1 ) , R, delta
) ; tree[ v] = comb( tree[ v* 2 ] , tree[ v* 2 + 1 ] ) ;
}
private void propagate( int v)
{
//tree[v] already has lazy[v]
if ( lazy[ v] == 0 )
return ;
tree[ v* 2 ] += lazy[ v] ;
lazy[ v* 2 ] += lazy[ v] ;
tree[ v* 2 + 1 ] += lazy[ v] ;
lazy[ v* 2 + 1 ] += lazy[ v] ;
lazy[ v] = 0 ;
}
private int comb( int a, int b)
{
}
}
class RangeBit
{
//FenwickTree and RangeBit are faster than LazySegTree by constant factor
final int [ ] value;
final int [ ] weightedVal;
public RangeBit( int treeTo)
{
value = new int [ treeTo+ 2 ] ;
weightedVal = new int [ treeTo+ 2 ] ;
}
private void updateHelper( int index, int delta)
{
int weightedDelta = index* delta;
for ( int j = index; j < value.length ; j += j & - j)
{
value[ j] += delta;
weightedVal[ j] += weightedDelta;
}
}
public void update( int from, int to, int delta)
{
updateHelper( from, delta) ;
updateHelper( to + 1 , - delta) ;
}
private int query( int to)
{
int res = 0 ;
int weightedRes = 0 ;
for ( int j = to; j > 0 ; j -= j & - j)
{
res += value[ j] ;
weightedRes += weightedVal[ j] ;
}
return ( ( to + 1 ) * res) - weightedRes;
}
public int query( int from, int to)
{
if ( to < from)
return 0 ;
return query( to) - query( from - 1 ) ;
}
}
class SparseTable
{
public int [ ] log;
public int [ ] [ ] table;
public int N; public int K;
public SparseTable( int N)
{
this .N = N;
log = new int [ N+ 2 ] ;
table = new int [ N] [ K+ 1 ] ;
sparsywarsy( ) ;
}
private void sparsywarsy( )
{
log[ 1 ] = 0 ;
for ( int i= 2 ; i <= N+ 1 ; i++ )
log[ i] = log[ i/ 2 ] + 1 ;
}
public void lift( int [ ] arr)
{
int n = arr.length ;
for ( int i= 0 ; i < n; i++ )
table[ i] [ 0 ] = arr[ i] ;
for ( int j= 1 ; j <= K; j++ )
for ( int i= 0 ; i + ( 1 << j) <= n; i++ )
table
[ i
] [ j
] = Math .
min ( table
[ i
] [ j
- 1 ] , table
[ i
+ ( 1 << ( j
- 1 ) ) ] [ j
- 1 ] ) ; }
public int query( int L, int R)
{
//inclusive, 1 indexed
L--; R--;
int mexico = log[ R- L+ 1 ] ;
return Math .
min ( table
[ L
] [ mexico
] , table
[ R
- ( 1 << mexico
) + 1 ] [ mexico
] ) ; }
}
class LCA
{
public int N, root;
public ArrayDeque< Integer> [ ] edges;
private int [ ] enter;
private int [ ] exit;
private int LOG = 17 ; //change this
private int [ ] [ ] dp;
public LCA( int n, ArrayDeque< Integer> [ ] edges, int r)
{
N = n; root = r;
enter = new int [ N+ 1 ] ;
exit = new int [ N+ 1 ] ;
dp = new int [ N+ 1 ] [ LOG] ;
this .edges = edges;
int [ ] time = new int [ 1 ] ;
//change to iterative dfs if N is large
dfs( root, 0 , time) ;
dp[ root] [ 0 ] = 1 ;
for ( int b= 1 ; b < LOG; b++ )
for ( int v= 1 ; v <= N; v++ )
dp[ v] [ b] = dp[ dp[ v] [ b- 1 ] ] [ b- 1 ] ;
}
private void dfs( int curr, int par, int [ ] time)
{
dp[ curr] [ 0 ] = par;
enter[ curr] = ++ time[ 0 ] ;
for ( int next: edges[ curr] )
if ( next != par)
dfs( next, curr, time) ;
exit[ curr] = ++ time[ 0 ] ;
}
public int lca( int x, int y)
{
if ( isAnc( x, y) )
return x;
if ( isAnc( y, x) )
return y;
int curr = x;
for ( int b= LOG- 1 ; b >= 0 ; b-- )
{
int temp = dp[ curr] [ b] ;
if ( ! isAnc( temp, y) )
curr = temp;
}
return dp[ curr] [ 0 ] ;
}
private boolean isAnc( int anc, int curr)
{
return enter[ anc] <= enter[ curr] && exit[ anc] >= exit[ curr] ;
}
}
{
private int CONS = 62 ; //safe
public long [ ] sets;
public int size;
{
size = N;
if ( N% CONS == 0 )
sets = new long [ N/ CONS] ;
else
sets = new long [ N/ CONS+ 1 ] ;
}
public void add( int i)
{
int dex = i/ CONS;
int thing = i% CONS;
sets[ dex] |= ( 1L << thing) ;
}
{
int boof
= Math .
min ( sets.
length , oth.
sets .
length ) ; int res = 0 ;
for ( int i= 0 ; i < boof; i++ )
res
+= Long .
bitCount ( sets
[ i
] & oth.
sets [ i
] ) ; return res;
}
{
int boof
= Math .
min ( sets.
length , oth.
sets .
length ) ; int res = 0 ;
for ( int i= 0 ; i < boof; i++ )
res
+= Long .
bitCount ( sets
[ i
] ^ oth.
sets [ i
] ) ; return res;
}
}
class MaxFlow
{
//Dinic with optimizations (see magic array in dfs function)
public int N, source, sink;
public ArrayList< Edge> [ ] edges;
private int [ ] depth;
public MaxFlow( int n, int x, int y)
{
N = n;
source = x;
sink = y;
for ( int i= 0 ; i <= N; i++ )
edges[ i] = new ArrayList< Edge> ( ) ;
depth = new int [ N+ 1 ] ;
}
public void addEdge( int from, int to, long cap)
{
Edge forward = new Edge( from, to, cap) ;
Edge backward = new Edge( to, from, 0L) ;
forward.residual = backward;
backward.residual = forward;
edges[ from] .add ( forward) ;
edges[ to] .add ( backward) ;
}
public long mfmc( )
{
long res = 0L;
int [ ] magic = new int [ N+ 1 ] ;
while ( assignDepths( ) )
{
long flow
= dfs
( source,
Long .
MAX_VALUE / 2 , magic
) ; while ( flow > 0 )
{
res += flow;
flow
= dfs
( source,
Long .
MAX_VALUE / 2 , magic
) ; }
magic = new int [ N+ 1 ] ;
}
return res;
}
private boolean assignDepths( )
{
ArrayDeque< Integer> q = new ArrayDeque< Integer> ( ) ;
q.add ( source) ;
depth[ source] = 0 ;
while ( q.size ( ) > 0 )
{
int curr = q.poll ( ) ;
for ( Edge e: edges[ curr] )
if ( e.capacityLeft ( ) > 0 && depth[ e.to ] == - 69 )
{
depth[ e.to ] = depth[ curr] + 1 ;
q.add ( e.to ) ;
}
}
return depth[ sink] != - 69 ;
}
private long dfs( int curr, long bottleneck, int [ ] magic)
{
if ( curr == sink)
return bottleneck;
for ( ; magic[ curr] < edges[ curr] .size ( ) ; magic[ curr] ++ )
{
Edge e = edges[ curr] .get ( magic[ curr] ) ;
if ( e.capacityLeft ( ) > 0 && depth[ e.to ] - depth[ curr] == 1 )
{
long val
= dfs
( e.
to ,
Math .
min ( bottleneck, e.
capacityLeft ( ) ) , magic
) ; if ( val > 0 )
{
e.augment ( val) ;
return val;
}
}
}
return 0L; //no flow
}
private class Edge
{
public int from, to;
public long flow, capacity;
public Edge residual;
public Edge( int f, int t, long cap)
{
from = f;
to = t;
capacity = cap;
}
public long capacityLeft( )
{
return capacity- flow;
}
public void augment( long val)
{
flow += val;
residual.flow -= val;
}
}
}
class FastReader
{
public FastReader( )
{
}
{
while ( st == null || ! st.hasMoreElements ( ) )
{
try
{
}
{
e.printStackTrace ( ) ;
}
}
return st.nextToken ( ) ;
}
int nextInt( )
{
}
long nextLong( )
{
return Long .
parseLong ( next
( ) ) ; }
double nextDouble( )
{
return Double .
parseDouble ( next
( ) ) ; }
{
try
{
str = br.readLine ( ) ;
}
{
e.printStackTrace ( ) ;
}
return str;
}
}
LyogcGFja2FnZSBjb2RlY2hlZjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KY2xhc3MgTWFpbgp7CiAgICBzdGF0aWMgQnVmZmVyZWRXcml0ZXIgcHV0ID0gbmV3IEJ1ZmZlcmVkV3JpdGVyKG5ldyBPdXRwdXRTdHJlYW1Xcml0ZXIoU3lzdGVtLm91dCkpOwogICAgc3RhdGljIGludCBpbnRtYXggPSBJbnRlZ2VyLk1BWF9WQUxVRTsKICAgIHN0YXRpYyBpbnQgaW50bWluID0gSW50ZWdlci5NSU5fVkFMVUU7CiAgICBzdGF0aWMgbG9uZyBtb2QgPSAxMDAwMDAwMDA3TDsKICAgIAogICAgcHVibGljIHN0YXRpYyB2b2lkIG1haW4gKFN0cmluZ1tdIGFyZ3MpIHRocm93cyBqYXZhLmxhbmcuRXhjZXB0aW9uCgl7CgkgICAgRmFzdFJlYWRlciBnZXQgPSBuZXcgRmFzdFJlYWRlcigpOwoJICAgIAoJICAgIGludCBUID0gZ2V0Lm5leHRJbnQoKTsKCSAgICAKCSAgICB3aGlsZShULS0+MCkKCSAgICB7CgkgICAgCWludCBtPWdldC5uZXh0SW50KCksIG49Z2V0Lm5leHRJbnQoKTsKCSAgICAJCgkgICAgCWludCBbXSBYID0gbmV3IGludFttLTFdOwoJICAgIAlpbnQgW10gWSA9IG5ldyBpbnRbbi0xXTsKCSAgICAJCgkgICAgCWZvcihpbnQgaT0wOyBpPG0tMTsgaSsrKSBYW2ldPWdldC5uZXh0SW50KCk7CgkgICAgCWZvcihpbnQgaT0wOyBpPG4tMTsgaSsrKSBZW2ldPWdldC5uZXh0SW50KCk7CgkgICAgICAgIAoJICAgICAgICBhbnMoIFgsIFksIG0sIG4gKTsKCSAgICAgICAgCgkgICAgICAgIHB1dC5mbHVzaCgpOwoJICAgIH0KCSAgICAKCSAgICBwdXQuY2xvc2UoKTsKCX0KCQoJcHVibGljIHN0YXRpYyB2b2lkIGFucyggaW50W10gWCwgaW50W10gWSwgaW50IG0sIGludCBuICkgdGhyb3dzIGphdmEubGFuZy5FeGNlcHRpb24KCXsKCQlBcnJheUxpc3Q8UGFpcj4gcHAgPSBuZXcgQXJyYXlMaXN0PD4oKTsKICAgICAgICAKICAgICAgICBmb3IoIGludCBpPTA7IGk8WC5sZW5ndGg7IGkrKykgcHAuYWRkKG5ldyBQYWlyKFhbaV0sIDEpKTsKICAgICAgICBmb3IoIGludCBpPTA7IGk8WS5sZW5ndGg7IGkrKykgcHAuYWRkKG5ldyBQYWlyKFlbaV0sIDIpKTsKICAgICAgICAKICAgICAgICBpbnQgdl9jdXRzID0gMSwgaF9jdXRzID0xOwogICAgICAgIGxvbmcgY29zdCA9MDsKICAgICAgICAKICAgICAgICBDb2xsZWN0aW9ucy5zb3J0KHBwKTsKICAgICAgICAKICAgICAgICBmb3IoaW50IGk9MDsgaTxwcC5zaXplKCk7IGkrKykKICAgICAgICB7CiAgICAgICAgICAgIFBhaXIgcCA9IHBwLmdldChpKTsKICAgICAgICAgICAgCiAgICAgICAgICAgIGlmKHAuYiA9PSAyKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBjb3N0ICs9IChsb25nKXAuYSp2X2N1dHM7CiAgICAgICAgICAgICAgICBoX2N1dHMrKzsKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGNvc3QgKz0gKGxvbmcpcC5hKmhfY3V0czsKICAgICAgICAgICAgICAgIHZfY3V0cysrOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIAogICAgICAgIHB1dC53cml0ZShjb3N0KyJcbiIpOwoJfQoJCgkvLwoJLy8gRlVOQ1RJT05TIEJFTE9XIDoKCS8vIGlzUHJpbWUoKSwgbGNtKCksIGdjZCgpLCB0b3RpZW50KCksIGZpbmREaXYoKSwgc29ydEludCgpLCBzb3J0TG9uZygpLAoJLy8gcG93ZXIoKSwgZnJlcUFycigpLCBNQVRSSVg6IG11bHRpcGx5KCksIHBvd2VyKCkKCS8vIENMQVNTRVMgQkVMT1cgOgoJLy8gRFNVLCBGZW53aWNrVHJlZSwgU2VnbWVudFRyZWUsIExhenlTZWdUcmVlLCBSYW5nZUJpdCwgU3BhcnNlVGFibGUsIExDQSwgQml0U2V0LCBNYXhGbG93CgkvLwoJCglwdWJsaWMgc3RhdGljIGludFtdIHJlYWRBcnIoaW50IE4sIEZhc3RSZWFkZXIgZ2V0KSB0aHJvd3MgRXhjZXB0aW9uCiAgICB7CiAgICAgICAgaW50W10gYXJyID0gbmV3IGludFtOXTsKICAgICAgICBTdHJpbmdUb2tlbml6ZXIgc3QgPSBuZXcgU3RyaW5nVG9rZW5pemVyKGdldC5uZXh0TGluZSgpLCAiICIpOwogICAgICAgIGZvcihpbnQgaT0wOyBpIDwgTjsgaSsrKSBhcnJbaV0gPSBJbnRlZ2VyLnBhcnNlSW50KHN0Lm5leHRUb2tlbigpKTsKICAgICAgICAKICAgICAgICByZXR1cm4gYXJyOwogICAgfQogICAgCiAgICBwdWJsaWMgc3RhdGljIGxvbmdbXSByZWFkQXJyMihpbnQgTiwgRmFzdFJlYWRlciBnZXQpIHRocm93cyBFeGNlcHRpb24KICAgIHsKICAgICAgICBsb25nW10gYXJyID0gbmV3IGxvbmdbTl07CiAgICAgICAgU3RyaW5nVG9rZW5pemVyIHN0ID0gbmV3IFN0cmluZ1Rva2VuaXplcihnZXQubmV4dExpbmUoKSwgIiAiKTsKICAgICAgICBmb3IoaW50IGk9MDsgaSA8IE47IGkrKykgYXJyW2ldID0gTG9uZy5wYXJzZUxvbmcoc3QubmV4dFRva2VuKCkpOwogICAgICAgIAogICAgICAgIHJldHVybiBhcnI7CiAgICB9CiAgICAKICAgIHB1YmxpYyBzdGF0aWMgaW50W11bXSByZWFkTWF0KGludCBOLCBpbnQgTSwgRmFzdFJlYWRlciBnZXQpIHRocm93cyBFeGNlcHRpb24KICAgIHsKICAgICAgICBpbnQgW11bXSBtYXQgPSBuZXcgaW50W05dW01dOwogICAgICAgIAogICAgICAgIGZvcihpbnQgaT0wOyBpIDwgTjsgaSsrKQogICAgICAgIHsKICAgICAgICAgICAgU3RyaW5nVG9rZW5pemVyIHN0ID0gbmV3IFN0cmluZ1Rva2VuaXplcihnZXQubmV4dExpbmUoKSwgIiAiKTsKICAgICAgICAgICAgZm9yKGludCBqPTA7IGogPCBNOyBqKyspIG1hdFtpXVtqXSA9IEludGVnZXIucGFyc2VJbnQoc3QubmV4dFRva2VuKCkpOwogICAgICAgIH0KICAgICAgICAKICAgICAgICByZXR1cm4gbWF0OwogICAgfQogICAgCiAgICBwdWJsaWMgc3RhdGljIHZvaWQgcHJpbnQoaW50W10gYXJyKSB0aHJvd3MgamF2YS5sYW5nLkV4Y2VwdGlvbgogICAgewogICAgICAgIGZvcihpbnQgeDogYXJyKQogICAgICAgICAgICBwdXQud3JpdGUoeCsiICIpOwogICAgICAgIHB1dC53cml0ZSgiXG4iKTsKICAgIH0KICAgIAogICAgcHVibGljIHN0YXRpYyB2b2lkIHByaW50TWF0KGludFtdW10gYXJyKSB0aHJvd3MgamF2YS5sYW5nLkV4Y2VwdGlvbgogICAgewogICAgICAgIGZvcihpbnQgaT0wOyBpIDwgYXJyLmxlbmd0aDsgaSsrKQogICAgICAgIHsKICAgICAgICAgICAgZm9yKGludCBqPTA7IGogPCBhcnJbMF0ubGVuZ3RoOyBqKyspCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHB1dC53cml0ZShhcnJbaV1bal0gKyAiICIpOwogICAgICAgICAgICB9CiAgICAgICAgICAgIHB1dC53cml0ZSgiXG4iKTsKICAgICAgICB9CiAgICAgICAgcHV0LndyaXRlKCJcbiIpOwogICAgfQoJCiAgICBwdWJsaWMgc3RhdGljIGJvb2xlYW4gaXNQcmltZShsb25nIG4pCiAgICB7CiAgICAgICAgaWYobiA8IDIpIHJldHVybiBmYWxzZTsKICAgICAgICBpZihuID09IDIgfHwgbiA9PSAzKSByZXR1cm4gdHJ1ZTsKICAgICAgICBpZihuJTIgPT0gMCB8fCBuJTMgPT0gMCkgcmV0dXJuIGZhbHNlOwogICAgICAgIGxvbmcgc3FydE4gPSAobG9uZylNYXRoLnNxcnQobikrMTsKICAgICAgICBmb3IobG9uZyBpID0gNkw7IGkgPD0gc3FydE47IGkgKz0gNikgewogICAgICAgICAgICBpZihuJShpLTEpID09IDAgfHwgbiUoaSsxKSA9PSAwKSByZXR1cm4gZmFsc2U7CiAgICAgICAgfQogICAgICAgIHJldHVybiB0cnVlOwogICAgfQogICAgCiAgICBwdWJsaWMgc3RhdGljIGxvbmcgbGNtKGxvbmcgYSwgbG9uZyBiKQogICAgewogICAgICAgIHJldHVybiAoYSAvIGdjZChhLCBiKSkgKiBiOwogICAgfQogICAgCiAgICBwdWJsaWMgc3RhdGljIGxvbmcgZ2NkKGxvbmcgYSwgbG9uZyBiKQogICAgewogICAgICAgIGlmKGEgPiBiKSBhID0gKGErYiktKGI9YSk7CiAgICAgICAgaWYoYSA9PSAwTCkgcmV0dXJuIGI7CiAgICAgICAgCiAgICAgICAgcmV0dXJuIGdjZChiJWEsIGEpOwogICAgfQogICAgCiAgICBwdWJsaWMgc3RhdGljIGxvbmcgdG90aWVudChsb25nIG4pCiAgICB7CiAgICAgICAgbG9uZyByZXN1bHQgPSBuOwogICAgICAgIGZvciAoaW50IHAgPSAyOyBwKnAgPD0gbjsgKytwKQogICAgICAgICAgICBpZiAobiAlIHAgPT0gMCkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgd2hpbGUobiVwID09IDApCiAgICAgICAgICAgICAgICAgICAgbiAvPSBwOwogICAgICAgICAgICAgICAgcmVzdWx0IC09IHJlc3VsdC9wOwogICAgICAgICAgICB9CiAgICAgICAgaWYgKG4gPiAxKSByZXN1bHQgLT0gcmVzdWx0L247CiAgICAgICAgCiAgICAgICAgcmV0dXJuIHJlc3VsdDsKICAgIH0KICAgIAogICAgcHVibGljIHN0YXRpYyBBcnJheUxpc3Q8SW50ZWdlcj4gZmluZERpdihpbnQgTikKICAgIHsKICAgICAgICAvL2dldHMgYWxsIGRpdmlzb3JzIG9mIE4KICAgICAgICBBcnJheUxpc3Q8SW50ZWdlcj4gbHMxID0gbmV3IEFycmF5TGlzdDxJbnRlZ2VyPigpOwogICAgICAgIEFycmF5TGlzdDxJbnRlZ2VyPiBsczIgPSBuZXcgQXJyYXlMaXN0PEludGVnZXI+KCk7CiAgICAgICAgZm9yKGludCBpPTE7IGkgPD0gKGludCkoTWF0aC5zcXJ0KE4pKzAuMDAwMDAwMDEpOyBpKyspCiAgICAgICAgICAgIGlmKE4laSA9PSAwKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBsczEuYWRkKGkpOwogICAgICAgICAgICAgICAgbHMyLmFkZChOL2kpOwogICAgICAgICAgICB9CiAgICAgICAgQ29sbGVjdGlvbnMucmV2ZXJzZShsczIpOwogICAgICAgIGZvcihpbnQgYjogbHMyKQogICAgICAgICAgICBpZihiICE9IGxzMS5nZXQobHMxLnNpemUoKS0xKSkKICAgICAgICAgICAgICAgIGxzMS5hZGQoYik7CiAgICAgICAgcmV0dXJuIGxzMTsKICAgIH0KICAgIAogICAgcHVibGljIHN0YXRpYyB2b2lkIHNvcnRJbnQoaW50W10gYXJyKQogICAgewogICAgICAgIC8vYmVjYXVzZSBBcnJheXMuc29ydCgpIHVzZXMgcXVpY2tzb3J0IHdoaWNoIGlzIGR1bWIKICAgICAgICAvL0NvbGxlY3Rpb25zLnNvcnQoKSB1c2VzIG1lcmdlIHNvcnQKICAgICAgICAKICAgICAgICBBcnJheUxpc3Q8SW50ZWdlcj4gbHMgPSBuZXcgQXJyYXlMaXN0PEludGVnZXI+KCk7CiAgICAgICAgCiAgICAgICAgZm9yKGludCB4OiBhcnIpIGxzLmFkZCh4KTsKICAgICAgICAKICAgICAgICBDb2xsZWN0aW9ucy5zb3J0KGxzKTsKICAgICAgICBmb3IoaW50IGk9MDsgaSA8IGFyci5sZW5ndGg7IGkrKykgYXJyW2ldID0gbHMuZ2V0KGkpOwogICAgfQogICAgCiAgICBwdWJsaWMgc3RhdGljIHZvaWQgc29ydExvbmcobG9uZ1tdIGFycikKICAgIHsKICAgICAgICAvL2JlY2F1c2UgQXJyYXlzLnNvcnQoKSB1c2VzIHF1aWNrc29ydCB3aGljaCBpcyBkdW1iCiAgICAgICAgLy9Db2xsZWN0aW9ucy5zb3J0KCkgdXNlcyBtZXJnZSBzb3J0CiAgICAgICAgCiAgICAgICAgQXJyYXlMaXN0PExvbmc+IGxzID0gbmV3IEFycmF5TGlzdDxMb25nPigpOwogICAgICAgIAogICAgICAgIGZvcihsb25nIHg6IGFycikgbHMuYWRkKHgpOwogICAgICAgIAogICAgICAgIENvbGxlY3Rpb25zLnNvcnQobHMpOwogICAgICAgIGZvcihpbnQgaT0wOyBpIDwgYXJyLmxlbmd0aDsgaSsrKSBhcnJbaV0gPSBscy5nZXQoaSk7CiAgICB9CiAgICAKICAgIHB1YmxpYyBzdGF0aWMgdm9pZCBzb3J0Q2hhcihjaGFyW10gYXJyKQogICAgewogICAgICAgIC8vYmVjYXVzZSBBcnJheXMuc29ydCgpIHVzZXMgcXVpY2tzb3J0IHdoaWNoIGlzIGR1bWIKICAgICAgICAvL0NvbGxlY3Rpb25zLnNvcnQoKSB1c2VzIG1lcmdlIHNvcnQKICAgICAgICAKICAgICAgICBBcnJheUxpc3Q8Q2hhcmFjdGVyPiBscyA9IG5ldyBBcnJheUxpc3Q8Q2hhcmFjdGVyPigpOwogICAgICAgIAogICAgICAgIGZvcihjaGFyIHg6IGFycikgbHMuYWRkKHgpOwogICAgICAgIAogICAgICAgIENvbGxlY3Rpb25zLnNvcnQobHMpOwogICAgICAgIGZvcihpbnQgaT0wOyBpIDwgYXJyLmxlbmd0aDsgaSsrKSBhcnJbaV0gPSBscy5nZXQoaSk7CiAgICB9CiAgICAKICAgIHB1YmxpYyBzdGF0aWMgU3RyaW5nIHNvcnRTdHJpbmcoU3RyaW5nIGlucHV0U3RyaW5nKQogICAgewogICAgICAgIGNoYXIgdGVtcEFycmF5W10gPSBpbnB1dFN0cmluZy50b0NoYXJBcnJheSgpOwogICAgICAgIHNvcnRDaGFyKHRlbXBBcnJheSk7CiAgICAgICAgcmV0dXJuIG5ldyBTdHJpbmcodGVtcEFycmF5KTsKICAgIH0KICAgIAogICAgcHVibGljIHN0YXRpYyBsb25nIHBvd2VyKGxvbmcgeCwgbG9uZyB5LCBsb25nIHApCiAgICB7CiAgICAgICAgLy8wXjAgPSAxCiAgICAgICAgbG9uZyByZXMgPSAxTDsKICAgICAgICB4ID0geCVwOwogICAgICAgIHdoaWxlKHkgPiAwKQogICAgICAgIHsKICAgICAgICAgICAgaWYoKHkmMSk9PTEpCiAgICAgICAgICAgICAgICByZXMgPSAocmVzKngpJXA7CiAgICAgICAgICAgIHkgPj49IDE7CiAgICAgICAgICAgIHggPSAoeCp4KSVwOwogICAgICAgIH0KICAgICAgICByZXR1cm4gcmVzOwogICAgfQogICAgCiAgICAvL2N1c3RvbSBtdWx0aXNldCAocmVwbGFjZSB3aXRoIEhhc2hNYXAgaWYgbmVlZGVkKQogICAgcHVibGljIHN0YXRpYyB2b2lkIHB1c2goVHJlZU1hcDxJbnRlZ2VyLCBJbnRlZ2VyPiBtYXAsIGludCBrLCBpbnQgdikKICAgIHsKICAgICAgICAvL21hcFtrXSArPSB2OwogICAgICAgIGlmKCFtYXAuY29udGFpbnNLZXkoaykpIG1hcC5wdXQoaywgdik7CiAgICAgICAgZWxzZSBtYXAucHV0KGssIG1hcC5nZXQoaykrdik7CiAgICB9CiAgICAKICAgIHB1YmxpYyBzdGF0aWMgdm9pZCBwdWxsKFRyZWVNYXA8SW50ZWdlciwgSW50ZWdlcj4gbWFwLCBpbnQgaywgaW50IHYpCiAgICB7CiAgICAgICAgLy9hc3N1bWVzIG1hcFtrXSA+PSB2CiAgICAgICAgLy9tYXBba10gLT0gdgogICAgICAgIGludCBsb2wgPSBtYXAuZ2V0KGspOwogICAgICAgIAogICAgICAgIGlmKGxvbCA9PSB2KSBtYXAucmVtb3ZlKGspOwogICAgICAgIGVsc2UgbWFwLnB1dChrLCBsb2wtdik7CiAgICB9CiAgICAKICAgIHB1YmxpYyBzdGF0aWMgSGFzaE1hcDxJbnRlZ2VyLCBJbnRlZ2VyPiBmcmVxTWFwKGludFtdIGFycikKICAgIHsKICAgICAgICBIYXNoTWFwPEludGVnZXIsIEludGVnZXI+IG1hcCA9IG5ldyBIYXNoTWFwPEludGVnZXIsIEludGVnZXI+KCk7CiAgICAgICAgCiAgICAgICAgZm9yKGludCB4OiBhcnIpCiAgICAgICAgICAgIGlmKCFtYXAuY29udGFpbnNLZXkoeCkpIG1hcC5wdXQoeCwgbWFwLmdldCh4KSArIDEpOwogICAgICAgICAgICBlbHNlIG1hcC5wdXQoeCwgMSk7CiAgICAgICAgICAgIAogICAgICAgIHJldHVybiBtYXA7CiAgICB9CiAgICAKICAgIHB1YmxpYyBzdGF0aWMgbG9uZ1tdW10gbXVsdGlwbHkobG9uZ1tdW10gbGVmdCwgbG9uZ1tdW10gcmlnaHQpCiAgICB7CiAgICAgICAgbG9uZyBNT0QgPSAxMDAwMDAwMDA3TDsKICAgICAgICBpbnQgTiA9IGxlZnQubGVuZ3RoOwogICAgICAgIGludCBNID0gcmlnaHRbMF0ubGVuZ3RoOwogICAgICAgIGxvbmdbXVtdIHJlcyA9IG5ldyBsb25nW05dW01dOwogICAgICAgIGZvcihpbnQgYT0wOyBhIDwgTjsgYSsrKQogICAgICAgICAgICBmb3IoaW50IGI9MDsgYiA8IE07IGIrKykKICAgICAgICAgICAgICAgIGZvcihpbnQgYz0wOyBjIDwgbGVmdFswXS5sZW5ndGg7IGMrKykKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICByZXNbYV1bYl0gKz0gKGxlZnRbYV1bY10qcmlnaHRbY11bYl0pJU1PRDsKICAgICAgICAgICAgICAgICAgICBpZihyZXNbYV1bYl0gPj0gTU9EKQogICAgICAgICAgICAgICAgICAgICAgICByZXNbYV1bYl0gLT0gTU9EOwogICAgICAgICAgICAgICAgfQogICAgICAgIHJldHVybiByZXM7CiAgICB9CiAgICAKICAgIHB1YmxpYyBzdGF0aWMgbG9uZ1tdW10gcG93ZXIobG9uZ1tdW10gZ3JpZCwgbG9uZyBwb3cpCiAgICB7CiAgICAgICAgbG9uZ1tdW10gcmVzID0gbmV3IGxvbmdbZ3JpZC5sZW5ndGhdW2dyaWRbMF0ubGVuZ3RoXTsKICAgICAgICBmb3IoaW50IGk9MDsgaSA8IHJlcy5sZW5ndGg7IGkrKykKICAgICAgICAgICAgcmVzW2ldW2ldID0gMUw7CiAgICAgICAgbG9uZ1tdW10gY3VyciA9IGdyaWQuY2xvbmUoKTsKICAgICAgICB3aGlsZShwb3cgPiAwKQogICAgICAgIHsKICAgICAgICAgICAgaWYoKHBvdyYxTCkgPT0gMUwpCiAgICAgICAgICAgICAgICByZXMgPSBtdWx0aXBseShjdXJyLCByZXMpOwogICAgICAgICAgICBwb3cgPj49IDE7CiAgICAgICAgICAgIGN1cnIgPSBtdWx0aXBseShjdXJyLCBjdXJyKTsKICAgICAgICB9CiAgICAgICAgcmV0dXJuIHJlczsKICAgIH0KfQoKY2xhc3MgUGFpciBpbXBsZW1lbnRzIENvbXBhcmFibGU8UGFpcj4KewogICAgaW50IGEsIGI7CiAgICAKICAgIHB1YmxpYyBQYWlyKGludCBhLCBpbnQgYikKICAgIHsKICAgICAgICB0aGlzLmEgPSBhOwogICAgICAgIHRoaXMuYiA9IGI7CiAgICB9CiAgICAKICAgIEBPdmVycmlkZQogICAgcHVibGljIGludCBjb21wYXJlVG8oUGFpciBwKQogICAgewogICAgCWlmKHRoaXMuYSA+IHAuYSkgcmV0dXJuIC0xOwogICAgICAgIGVsc2UgaWYodGhpcy5hIDwgcC5hKSByZXR1cm4gMTsKICAgICAgICBlbHNlCiAgICAgICAgewogICAgICAgICAgICBpZih0aGlzLmIgPiBwLmIpIHJldHVybiAtMTsKICAgICAgICAgICAgZWxzZSByZXR1cm4gMTsKICAgICAgICB9CiAgICB9Cn0KCmNsYXNzIERTVQp7CiAgICBwdWJsaWMgaW50W10gZHN1OwogICAgcHVibGljIGludFtdIHNpemU7CiAKICAgIHB1YmxpYyBEU1UoaW50IE4pCiAgICB7CiAgICAgICAgZHN1ID0gbmV3IGludFtOKzFdOwogICAgICAgIHNpemUgPSBuZXcgaW50W04rMV07CiAgICAgICAgZm9yKGludCBpPTA7IGkgPD0gTjsgaSsrKQogICAgICAgIHsKICAgICAgICAgICAgZHN1W2ldID0gaTsKICAgICAgICAgICAgc2l6ZVtpXSA9IDE7CiAgICAgICAgfQogICAgfQogICAgLy93aXRoIHBhdGggY29tcHJlc3Npb24sIG5vIGZpbmQgYnkgcmFuawogICAgcHVibGljIGludCBmaW5kKGludCB4KQogICAgewogICAgICAgIHJldHVybiBkc3VbeF0gPT0geCA/IHggOiAoZHN1W3hdID0gZmluZChkc3VbeF0pKTsKICAgIH0KICAgIHB1YmxpYyB2b2lkIG1lcmdlKGludCB4LCBpbnQgeSkKICAgIHsKICAgICAgICBpbnQgZnggPSBmaW5kKHgpOwogICAgICAgIGludCBmeSA9IGZpbmQoeSk7CiAgICAgICAgZHN1W2Z4XSA9IGZ5OwogICAgfQogICAgcHVibGljIHZvaWQgbWVyZ2UoaW50IHgsIGludCB5LCBib29sZWFuIHNpemVkKQogICAgewogICAgICAgIGludCBmeCA9IGZpbmQoeCk7CiAgICAgICAgaW50IGZ5ID0gZmluZCh5KTsKICAgICAgICBzaXplW2Z5XSArPSBzaXplW2Z4XTsKICAgICAgICBkc3VbZnhdID0gZnk7CiAgICB9Cn0KCmNsYXNzIEZlbndpY2tUcmVlCnsKICAgIC8vQmluYXJ5IEluZGV4ZWQgVHJlZQogICAgLy8xIGluZGV4ZWQKICAgIHB1YmxpYyBpbnRbXSB0cmVlOwogICAgcHVibGljIGludCBzaXplOwogCiAgICBwdWJsaWMgRmVud2lja1RyZWUoaW50IHNpemUpCiAgICB7CiAgICAgICAgdGhpcy5zaXplID0gc2l6ZTsKICAgICAgICB0cmVlID0gbmV3IGludFtzaXplKzVdOwogICAgfQogICAgcHVibGljIHZvaWQgYWRkKGludCBpLCBpbnQgdikKICAgIHsKICAgICAgICB3aGlsZShpIDw9IHNpemUpCiAgICAgICAgewogICAgICAgICAgICB0cmVlW2ldICs9IHY7CiAgICAgICAgICAgIGkgKz0gaSYtaTsKICAgICAgICB9CiAgICB9CiAgICBwdWJsaWMgaW50IGZpbmQoaW50IGkpCiAgICB7CiAgICAgICAgaW50IHJlcyA9IDA7CiAgICAgICAgd2hpbGUoaSA+PSAxKQogICAgICAgIHsKICAgICAgICAgICAgcmVzICs9IHRyZWVbaV07CiAgICAgICAgICAgIGkgLT0gaSYtaTsKICAgICAgICB9CiAgICAgICAgcmV0dXJuIHJlczsKICAgIH0KICAgIHB1YmxpYyBpbnQgZmluZChpbnQgbCwgaW50IHIpCiAgICB7CiAgICAgICAgcmV0dXJuIGZpbmQociktZmluZChsLTEpOwogICAgfQp9CgpjbGFzcyBTZWdtZW50VHJlZQp7CiAgICAvL1RsYXRvYW5pJ3Mgc2VnbWVudCB0cmVlCiAgICAvL2l0ZXJhdGl2ZSBpbXBsZW1lbnRhdGlvbiA9IGxvdyBjb25zdGFudCBydW50aW1lIGZhY3RvcgogICAgLy9yYW5nZSBxdWVyeSwgbm9uIGxhenkKICAgIGZpbmFsIGludFtdIHZhbDsKICAgIGZpbmFsIGludCB0cmVlRnJvbTsKICAgIGZpbmFsIGludCBsZW5ndGg7CiAKICAgIHB1YmxpYyBTZWdtZW50VHJlZShpbnQgdHJlZUZyb20sIGludCB0cmVlVG8pCiAgICB7CiAgICAgICAgdGhpcy50cmVlRnJvbSA9IHRyZWVGcm9tOwogICAgICAgIGludCBsZW5ndGggPSB0cmVlVG8gLSB0cmVlRnJvbSArIDE7CiAgICAgICAgaW50IGw7CiAgICAgICAgZm9yIChsID0gMDsgKDEgPDwgbCkgPCBsZW5ndGg7IGwrKyk7CiAgICAgICAgdmFsID0gbmV3IGludFsxIDw8IChsICsgMSldOwogICAgICAgIHRoaXMubGVuZ3RoID0gMSA8PCBsOwogICAgfQogICAgcHVibGljIHZvaWQgdXBkYXRlKGludCBpbmRleCwgaW50IGRlbHRhKQogICAgewogICAgICAgIC8vcmVwbGFjZXMgdmFsdWUKICAgICAgICBpbnQgbm9kZSA9IGluZGV4IC0gdHJlZUZyb20gKyBsZW5ndGg7CiAgICAgICAgdmFsW25vZGVdID0gZGVsdGE7CiAgICAgICAgZm9yIChub2RlID4+PSAxOyBub2RlID4gMDsgbm9kZSA+Pj0gMSkKICAgICAgICAgICAgdmFsW25vZGVdID0gY29tYih2YWxbbm9kZSA8PCAxXSwgdmFsWyhub2RlIDw8IDEpICsgMV0pOwogICAgfQogICAgcHVibGljIGludCBxdWVyeShpbnQgZnJvbSwgaW50IHRvKQogICAgewogICAgICAgIC8vaW5jbHVzaXZlIGJvdW5kcwogICAgICAgIGlmICh0byA8IGZyb20pCiAgICAgICAgICAgIHJldHVybiAwOyAvLzAgb3IgMT8KICAgICAgICBmcm9tICs9IGxlbmd0aCAtIHRyZWVGcm9tOwogICAgICAgIHRvICs9IGxlbmd0aCAtIHRyZWVGcm9tICsgMTsKICAgICAgICAvLzAgb3IgMT8KICAgICAgICBpbnQgcmVzID0gMDsKICAgICAgICBmb3IgKDsgZnJvbSArIChmcm9tICYgLWZyb20pIDw9IHRvOyBmcm9tICs9IGZyb20gJiAtZnJvbSkKICAgICAgICAgICAgcmVzID0gY29tYihyZXMsIHZhbFtmcm9tIC8gKGZyb20gJiAtZnJvbSldKTsKICAgICAgICBmb3IgKDsgdG8gLSAodG8gJiAtdG8pID49IGZyb207IHRvIC09IHRvICYgLXRvKQogICAgICAgICAgICByZXMgPSBjb21iKHJlcywgdmFsWyh0byAtICh0byAmIC10bykpIC8gKHRvICYgLXRvKV0pOwogICAgICAgIHJldHVybiByZXM7CiAgICB9CiAgICBwdWJsaWMgaW50IGNvbWIoaW50IGEsIGludCBiKQogICAgewogICAgICAgIC8vY2hhbmdlIHRoaXMKICAgICAgICByZXR1cm4gTWF0aC5tYXgoYSxiKTsKICAgIH0KfQoKY2xhc3MgTGF6eVNlZ1RyZWUKewogICAgLy9kZWZpbml0aW9ucwogICAgcHJpdmF0ZSBpbnQgTlVMTCA9IC0xOwogICAgcHJpdmF0ZSBpbnRbXSB0cmVlOwogICAgcHJpdmF0ZSBpbnRbXSBsYXp5OwogICAgcHJpdmF0ZSBpbnQgbGVuZ3RoOwogCiAgICBwdWJsaWMgTGF6eVNlZ1RyZWUoaW50IE4pCiAgICB7CiAgICAgICAgbGVuZ3RoID0gTjsgICBpbnQgYjsKICAgICAgICBmb3IoYj0wOyAoMTw8YikgPCBsZW5ndGg7IGIrKyk7CiAgICAgICAgdHJlZSA9IG5ldyBpbnRbMTw8KGIrMSldOwogICAgICAgIGxhenkgPSBuZXcgaW50WzE8PChiKzEpXTsKICAgIH0KICAgIHB1YmxpYyBpbnQgcXVlcnkoaW50IGxlZnQsIGludCByaWdodCkKICAgIHsKICAgICAgICAvL2xlZnQgYW5kIHJpZ2h0IGFyZSAwLWluZGV4ZWQKICAgICAgICByZXR1cm4gZ2V0KDEsIDAsIGxlbmd0aC0xLCBsZWZ0LCByaWdodCk7CiAgICB9CiAgICBwcml2YXRlIGludCBnZXQoaW50IHYsIGludCBjdXJyTCwgaW50IGN1cnJSLCBpbnQgTCwgaW50IFIpCiAgICB7CiAgICAgICAgaWYoTCA+IFIpCiAgICAgICAgICAgIHJldHVybiBOVUxMOwogICAgICAgIGlmKEwgPD0gY3VyckwgJiYgY3VyclIgPD0gUikKICAgICAgICAgICAgcmV0dXJuIHRyZWVbdl07CiAgICAgICAgcHJvcGFnYXRlKHYpOwogICAgICAgIGludCBtaWQgPSAoY3VyckwrY3VyclIpLzI7CiAgICAgICAgcmV0dXJuIGNvbWIoZ2V0KHYqMiwgY3VyckwsIG1pZCwgTCwgTWF0aC5taW4oUiwgbWlkKSksCiAgICAgICAgICAgICAgICBnZXQodioyKzEsIG1pZCsxLCBjdXJyUiwgTWF0aC5tYXgoTCwgbWlkKzEpLCBSKSk7CiAgICB9CiAgICBwdWJsaWMgdm9pZCB1cGRhdGUoaW50IGxlZnQsIGludCByaWdodCwgaW50IGRlbHRhKQogICAgewogICAgICAgIGFkZCgxLCAwLCBsZW5ndGgtMSwgbGVmdCwgcmlnaHQsIGRlbHRhKTsKICAgIH0KICAgIHByaXZhdGUgdm9pZCBhZGQoaW50IHYsIGludCBjdXJyTCwgaW50IGN1cnJSLCBpbnQgTCwgaW50IFIsIGludCBkZWx0YSkKICAgIHsKICAgICAgICBpZihMID4gUikKICAgICAgICAgICAgcmV0dXJuOwogICAgICAgIGlmKGN1cnJMID09IEwgJiYgY3VyclIgPT0gUikKICAgICAgICB7CiAgICAgICAgICAgIC8vZXhhY3QgY292ZXJpbmcKICAgICAgICAgICAgdHJlZVt2XSArPSBkZWx0YTsKICAgICAgICAgICAgbGF6eVt2XSArPSBkZWx0YTsKICAgICAgICAgICAgcmV0dXJuOwogICAgICAgIH0KICAgICAgICBwcm9wYWdhdGUodik7CiAgICAgICAgaW50IG1pZCA9IChjdXJyTCtjdXJyUikvMjsKICAgICAgICBhZGQodioyLCBjdXJyTCwgbWlkLCBMLCBNYXRoLm1pbihSLCBtaWQpLCBkZWx0YSk7CiAgICAgICAgYWRkKHYqMisxLCBtaWQrMSwgY3VyclIsIE1hdGgubWF4KEwsIG1pZCsxKSwgUiwgZGVsdGEpOwogICAgICAgIHRyZWVbdl0gPSBjb21iKHRyZWVbdioyXSwgdHJlZVt2KjIrMV0pOwogICAgfQogICAgcHJpdmF0ZSB2b2lkIHByb3BhZ2F0ZShpbnQgdikKICAgIHsKICAgICAgICAvL3RyZWVbdl0gYWxyZWFkeSBoYXMgbGF6eVt2XQogICAgICAgIGlmKGxhenlbdl0gPT0gMCkKICAgICAgICAgICAgcmV0dXJuOwogICAgICAgIHRyZWVbdioyXSArPSBsYXp5W3ZdOwogICAgICAgIGxhenlbdioyXSArPSBsYXp5W3ZdOwogICAgICAgIHRyZWVbdioyKzFdICs9IGxhenlbdl07CiAgICAgICAgbGF6eVt2KjIrMV0gKz0gbGF6eVt2XTsKICAgICAgICBsYXp5W3ZdID0gMDsKICAgIH0KICAgIHByaXZhdGUgaW50IGNvbWIoaW50IGEsIGludCBiKQogICAgewogICAgICAgIHJldHVybiBNYXRoLm1heChhLGIpOwogICAgfQp9CgpjbGFzcyBSYW5nZUJpdAp7CiAgICAvL0ZlbndpY2tUcmVlIGFuZCBSYW5nZUJpdCBhcmUgZmFzdGVyIHRoYW4gTGF6eVNlZ1RyZWUgYnkgY29uc3RhbnQgZmFjdG9yCiAgICBmaW5hbCBpbnRbXSB2YWx1ZTsKICAgIGZpbmFsIGludFtdIHdlaWdodGVkVmFsOwogCiAgICBwdWJsaWMgUmFuZ2VCaXQoaW50IHRyZWVUbykKICAgIHsKICAgICAgICB2YWx1ZSA9IG5ldyBpbnRbdHJlZVRvKzJdOwogICAgICAgIHdlaWdodGVkVmFsID0gbmV3IGludFt0cmVlVG8rMl07CiAgICB9CiAgICBwcml2YXRlIHZvaWQgdXBkYXRlSGVscGVyKGludCBpbmRleCwgaW50IGRlbHRhKQogICAgewogICAgICAgIGludCB3ZWlnaHRlZERlbHRhID0gaW5kZXgqZGVsdGE7CiAgICAgICAgZm9yKGludCBqID0gaW5kZXg7IGogPCB2YWx1ZS5sZW5ndGg7IGogKz0gaiAmIC1qKQogICAgICAgIHsKICAgICAgICAgICAgdmFsdWVbal0gKz0gZGVsdGE7CiAgICAgICAgICAgIHdlaWdodGVkVmFsW2pdICs9IHdlaWdodGVkRGVsdGE7CiAgICAgICAgfQogICAgfQogICAgcHVibGljIHZvaWQgdXBkYXRlKGludCBmcm9tLCBpbnQgdG8sIGludCBkZWx0YSkKICAgIHsKICAgICAgICB1cGRhdGVIZWxwZXIoZnJvbSwgZGVsdGEpOwogICAgICAgIHVwZGF0ZUhlbHBlcih0byArIDEsIC1kZWx0YSk7CiAgICB9CiAgICBwcml2YXRlIGludCBxdWVyeShpbnQgdG8pCiAgICB7CiAgICAgICAgaW50IHJlcyA9IDA7CiAgICAgICAgaW50IHdlaWdodGVkUmVzID0gMDsKICAgICAgICBmb3IgKGludCBqID0gdG87IGogPiAwOyBqIC09IGogJiAtaikKICAgICAgICB7CiAgICAgICAgICAgIHJlcyArPSB2YWx1ZVtqXTsKICAgICAgICAgICAgd2VpZ2h0ZWRSZXMgKz0gd2VpZ2h0ZWRWYWxbal07CiAgICAgICAgfQogICAgICAgIHJldHVybiAoKHRvICsgMSkqcmVzKS13ZWlnaHRlZFJlczsKICAgIH0KICAgIHB1YmxpYyBpbnQgcXVlcnkoaW50IGZyb20sIGludCB0bykKICAgIHsKICAgICAgICBpZiAodG8gPCBmcm9tKQogICAgICAgICAgICByZXR1cm4gMDsKICAgICAgICByZXR1cm4gcXVlcnkodG8pIC0gcXVlcnkoZnJvbSAtIDEpOwogICAgfQp9CgpjbGFzcyBTcGFyc2VUYWJsZQp7CiAgICBwdWJsaWMgaW50W10gbG9nOwogICAgcHVibGljIGludFtdW10gdGFibGU7CiAgICBwdWJsaWMgaW50IE47ICBwdWJsaWMgaW50IEs7CiAKICAgIHB1YmxpYyBTcGFyc2VUYWJsZShpbnQgTikKICAgIHsKICAgICAgICB0aGlzLk4gPSBOOwogICAgICAgIGxvZyA9IG5ldyBpbnRbTisyXTsKICAgICAgICBLID0gSW50ZWdlci5udW1iZXJPZlRyYWlsaW5nWmVyb3MoSW50ZWdlci5oaWdoZXN0T25lQml0KE4pKTsKICAgICAgICB0YWJsZSA9IG5ldyBpbnRbTl1bSysxXTsKICAgICAgICBzcGFyc3l3YXJzeSgpOwogICAgfQogICAgcHJpdmF0ZSB2b2lkIHNwYXJzeXdhcnN5KCkKICAgIHsKICAgICAgICBsb2dbMV0gPSAwOwogICAgICAgIGZvcihpbnQgaT0yOyBpIDw9IE4rMTsgaSsrKQogICAgICAgICAgICBsb2dbaV0gPSBsb2dbaS8yXSsxOwogICAgfQogICAgcHVibGljIHZvaWQgbGlmdChpbnRbXSBhcnIpCiAgICB7CiAgICAgICAgaW50IG4gPSBhcnIubGVuZ3RoOwogICAgICAgIGZvcihpbnQgaT0wOyBpIDwgbjsgaSsrKQogICAgICAgICAgICB0YWJsZVtpXVswXSA9IGFycltpXTsKICAgICAgICBmb3IoaW50IGo9MTsgaiA8PSBLOyBqKyspCiAgICAgICAgICAgIGZvcihpbnQgaT0wOyBpICsgKDEgPDwgaikgPD0gbjsgaSsrKQogICAgICAgICAgICAgICAgdGFibGVbaV1bal0gPSBNYXRoLm1pbih0YWJsZVtpXVtqLTFdLCB0YWJsZVtpKygxIDw8IChqIC0gMSkpXVtqLTFdKTsKICAgIH0KICAgIHB1YmxpYyBpbnQgcXVlcnkoaW50IEwsIGludCBSKQogICAgewogICAgICAgIC8vaW5jbHVzaXZlLCAxIGluZGV4ZWQKICAgICAgICBMLS07ICBSLS07CiAgICAgICAgaW50IG1leGljbyA9IGxvZ1tSLUwrMV07CiAgICAgICAgcmV0dXJuIE1hdGgubWluKHRhYmxlW0xdW21leGljb10sIHRhYmxlW1ItKDEgPDwgbWV4aWNvKSsxXVttZXhpY29dKTsKICAgIH0KfQoKY2xhc3MgTENBCnsKICAgIHB1YmxpYyBpbnQgTiwgcm9vdDsKICAgIHB1YmxpYyBBcnJheURlcXVlPEludGVnZXI+W10gZWRnZXM7CiAgICBwcml2YXRlIGludFtdIGVudGVyOwogICAgcHJpdmF0ZSBpbnRbXSBleGl0OwogICAgcHJpdmF0ZSBpbnQgTE9HID0gMTc7IC8vY2hhbmdlIHRoaXMKICAgIHByaXZhdGUgaW50W11bXSBkcDsKIAogICAgcHVibGljIExDQShpbnQgbiwgQXJyYXlEZXF1ZTxJbnRlZ2VyPltdIGVkZ2VzLCBpbnQgcikKICAgIHsKICAgICAgICBOID0gbjsgICByb290ID0gcjsKICAgICAgICBlbnRlciA9IG5ldyBpbnRbTisxXTsKICAgICAgICBleGl0ID0gbmV3IGludFtOKzFdOwogICAgICAgIGRwID0gbmV3IGludFtOKzFdW0xPR107CiAgICAgICAgdGhpcy5lZGdlcyA9IGVkZ2VzOwogICAgICAgIGludFtdIHRpbWUgPSBuZXcgaW50WzFdOwogICAgICAgIC8vY2hhbmdlIHRvIGl0ZXJhdGl2ZSBkZnMgaWYgTiBpcyBsYXJnZQogICAgICAgIGRmcyhyb290LCAwLCB0aW1lKTsKICAgICAgICBkcFtyb290XVswXSA9IDE7CiAgICAgICAgZm9yKGludCBiPTE7IGIgPCBMT0c7IGIrKykKICAgICAgICAgICAgZm9yKGludCB2PTE7IHYgPD0gTjsgdisrKQogICAgICAgICAgICAgICAgZHBbdl1bYl0gPSBkcFtkcFt2XVtiLTFdXVtiLTFdOwogICAgfQogICAgcHJpdmF0ZSB2b2lkIGRmcyhpbnQgY3VyciwgaW50IHBhciwgaW50W10gdGltZSkKICAgIHsKICAgICAgICBkcFtjdXJyXVswXSA9IHBhcjsKICAgICAgICBlbnRlcltjdXJyXSA9ICsrdGltZVswXTsKICAgICAgICBmb3IoaW50IG5leHQ6IGVkZ2VzW2N1cnJdKQogICAgICAgICAgICBpZihuZXh0ICE9IHBhcikKICAgICAgICAgICAgICAgIGRmcyhuZXh0LCBjdXJyLCB0aW1lKTsKICAgICAgICBleGl0W2N1cnJdID0gKyt0aW1lWzBdOwogICAgfQogICAgcHVibGljIGludCBsY2EoaW50IHgsIGludCB5KQogICAgewogICAgICAgIGlmKGlzQW5jKHgsIHkpKQogICAgICAgICAgICByZXR1cm4geDsKICAgICAgICBpZihpc0FuYyh5LCB4KSkKICAgICAgICAgICAgcmV0dXJuIHk7CiAgICAgICAgaW50IGN1cnIgPSB4OwogICAgICAgIGZvcihpbnQgYj1MT0ctMTsgYiA+PSAwOyBiLS0pCiAgICAgICAgewogICAgICAgICAgICBpbnQgdGVtcCA9IGRwW2N1cnJdW2JdOwogICAgICAgICAgICBpZighaXNBbmModGVtcCwgeSkpCiAgICAgICAgICAgICAgICBjdXJyID0gdGVtcDsKICAgICAgICB9CiAgICAgICAgcmV0dXJuIGRwW2N1cnJdWzBdOwogICAgfQogICAgcHJpdmF0ZSBib29sZWFuIGlzQW5jKGludCBhbmMsIGludCBjdXJyKQogICAgewogICAgICAgIHJldHVybiBlbnRlclthbmNdIDw9IGVudGVyW2N1cnJdICYmIGV4aXRbYW5jXSA+PSBleGl0W2N1cnJdOwogICAgfQp9CgpjbGFzcyBCaXRTZXQKewogICAgcHJpdmF0ZSBpbnQgQ09OUyA9IDYyOyAvL3NhZmUKICAgIHB1YmxpYyBsb25nW10gc2V0czsKICAgIHB1YmxpYyBpbnQgc2l6ZTsKIAogICAgcHVibGljIEJpdFNldChpbnQgTikKICAgIHsKICAgICAgICBzaXplID0gTjsKICAgICAgICBpZihOJUNPTlMgPT0gMCkKICAgICAgICAgICAgc2V0cyA9IG5ldyBsb25nW04vQ09OU107CiAgICAgICAgZWxzZQogICAgICAgICAgICBzZXRzID0gbmV3IGxvbmdbTi9DT05TKzFdOwogICAgfQogICAgcHVibGljIHZvaWQgYWRkKGludCBpKQogICAgewogICAgICAgIGludCBkZXggPSBpL0NPTlM7CiAgICAgICAgaW50IHRoaW5nID0gaSVDT05TOwogICAgICAgIHNldHNbZGV4XSB8PSAoMUwgPDwgdGhpbmcpOwogICAgfQogICAgcHVibGljIGludCBhbmQoQml0U2V0IG90aCkKICAgIHsKICAgICAgICBpbnQgYm9vZiA9IE1hdGgubWluKHNldHMubGVuZ3RoLCBvdGguc2V0cy5sZW5ndGgpOwogICAgICAgIGludCByZXMgPSAwOwogICAgICAgIGZvcihpbnQgaT0wOyBpIDwgYm9vZjsgaSsrKQogICAgICAgICAgICByZXMgKz0gTG9uZy5iaXRDb3VudChzZXRzW2ldICYgb3RoLnNldHNbaV0pOwogICAgICAgIHJldHVybiByZXM7CiAgICB9CiAgICBwdWJsaWMgaW50IHhvcihCaXRTZXQgb3RoKQogICAgewogICAgICAgIGludCBib29mID0gTWF0aC5taW4oc2V0cy5sZW5ndGgsIG90aC5zZXRzLmxlbmd0aCk7CiAgICAgICAgaW50IHJlcyA9IDA7CiAgICAgICAgZm9yKGludCBpPTA7IGkgPCBib29mOyBpKyspCiAgICAgICAgICAgIHJlcyArPSBMb25nLmJpdENvdW50KHNldHNbaV0gXiBvdGguc2V0c1tpXSk7CiAgICAgICAgcmV0dXJuIHJlczsKICAgIH0KfQoKY2xhc3MgTWF4Rmxvdwp7CiAgICAvL0RpbmljIHdpdGggb3B0aW1pemF0aW9ucyAoc2VlIG1hZ2ljIGFycmF5IGluIGRmcyBmdW5jdGlvbikKICAgIHB1YmxpYyBpbnQgTiwgc291cmNlLCBzaW5rOwogICAgcHVibGljIEFycmF5TGlzdDxFZGdlPltdIGVkZ2VzOwogICAgcHJpdmF0ZSBpbnRbXSBkZXB0aDsKIAogICAgcHVibGljIE1heEZsb3coaW50IG4sIGludCB4LCBpbnQgeSkKICAgIHsKICAgICAgICBOID0gbjsKICAgICAgICBzb3VyY2UgPSB4OwogICAgICAgIHNpbmsgPSB5OwogICAgICAgIGVkZ2VzID0gbmV3IEFycmF5TGlzdFtOKzFdOwogICAgICAgIGZvcihpbnQgaT0wOyBpIDw9IE47IGkrKykKICAgICAgICAgICAgZWRnZXNbaV0gPSBuZXcgQXJyYXlMaXN0PEVkZ2U+KCk7CiAgICAgICAgZGVwdGggPSBuZXcgaW50W04rMV07CiAgICB9CiAgICBwdWJsaWMgdm9pZCBhZGRFZGdlKGludCBmcm9tLCBpbnQgdG8sIGxvbmcgY2FwKQogICAgewogICAgICAgIEVkZ2UgZm9yd2FyZCA9IG5ldyBFZGdlKGZyb20sIHRvLCBjYXApOwogICAgICAgIEVkZ2UgYmFja3dhcmQgPSBuZXcgRWRnZSh0bywgZnJvbSwgMEwpOwogICAgICAgIGZvcndhcmQucmVzaWR1YWwgPSBiYWNrd2FyZDsKICAgICAgICBiYWNrd2FyZC5yZXNpZHVhbCA9IGZvcndhcmQ7CiAgICAgICAgZWRnZXNbZnJvbV0uYWRkKGZvcndhcmQpOwogICAgICAgIGVkZ2VzW3RvXS5hZGQoYmFja3dhcmQpOwogICAgfQogICAgcHVibGljIGxvbmcgbWZtYygpCiAgICB7CiAgICAgICAgbG9uZyByZXMgPSAwTDsKICAgICAgICBpbnRbXSBtYWdpYyA9IG5ldyBpbnRbTisxXTsKICAgICAgICB3aGlsZShhc3NpZ25EZXB0aHMoKSkKICAgICAgICB7CiAgICAgICAgICAgIGxvbmcgZmxvdyA9IGRmcyhzb3VyY2UsIExvbmcuTUFYX1ZBTFVFLzIsIG1hZ2ljKTsKICAgICAgICAgICAgd2hpbGUoZmxvdyA+IDApCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHJlcyArPSBmbG93OwogICAgICAgICAgICAgICAgZmxvdyA9IGRmcyhzb3VyY2UsIExvbmcuTUFYX1ZBTFVFLzIsIG1hZ2ljKTsKICAgICAgICAgICAgfQogICAgICAgICAgICBtYWdpYyA9IG5ldyBpbnRbTisxXTsKICAgICAgICB9CiAgICAgICAgcmV0dXJuIHJlczsKICAgIH0KICAgIHByaXZhdGUgYm9vbGVhbiBhc3NpZ25EZXB0aHMoKQogICAgewogICAgICAgIEFycmF5cy5maWxsKGRlcHRoLCAtNjkpOwogICAgICAgIEFycmF5RGVxdWU8SW50ZWdlcj4gcSA9IG5ldyBBcnJheURlcXVlPEludGVnZXI+KCk7CiAgICAgICAgcS5hZGQoc291cmNlKTsKICAgICAgICBkZXB0aFtzb3VyY2VdID0gMDsKICAgICAgICB3aGlsZShxLnNpemUoKSA+IDApCiAgICAgICAgewogICAgICAgICAgICBpbnQgY3VyciA9IHEucG9sbCgpOwogICAgICAgICAgICBmb3IoRWRnZSBlOiBlZGdlc1tjdXJyXSkKICAgICAgICAgICAgICAgIGlmKGUuY2FwYWNpdHlMZWZ0KCkgPiAwICYmIGRlcHRoW2UudG9dID09IC02OSkKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBkZXB0aFtlLnRvXSA9IGRlcHRoW2N1cnJdKzE7CiAgICAgICAgICAgICAgICAgICAgcS5hZGQoZS50byk7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIHJldHVybiBkZXB0aFtzaW5rXSAhPSAtNjk7CiAgICB9CiAgICBwcml2YXRlIGxvbmcgZGZzKGludCBjdXJyLCBsb25nIGJvdHRsZW5lY2ssIGludFtdIG1hZ2ljKQogICAgewogICAgICAgIGlmKGN1cnIgPT0gc2luaykKICAgICAgICAgICAgcmV0dXJuIGJvdHRsZW5lY2s7CiAgICAgICAgZm9yKDsgbWFnaWNbY3Vycl0gPCBlZGdlc1tjdXJyXS5zaXplKCk7IG1hZ2ljW2N1cnJdKyspCiAgICAgICAgewogICAgICAgICAgICBFZGdlIGUgPSBlZGdlc1tjdXJyXS5nZXQobWFnaWNbY3Vycl0pOwogICAgICAgICAgICBpZihlLmNhcGFjaXR5TGVmdCgpID4gMCAmJiBkZXB0aFtlLnRvXS1kZXB0aFtjdXJyXSA9PSAxKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBsb25nIHZhbCA9IGRmcyhlLnRvLCBNYXRoLm1pbihib3R0bGVuZWNrLCBlLmNhcGFjaXR5TGVmdCgpKSwgbWFnaWMpOwogICAgICAgICAgICAgICAgaWYodmFsID4gMCkKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBlLmF1Z21lbnQodmFsKTsKICAgICAgICAgICAgICAgICAgICByZXR1cm4gdmFsOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIHJldHVybiAwTDsgIC8vbm8gZmxvdwogICAgfQogICAgcHJpdmF0ZSBjbGFzcyBFZGdlCiAgICB7CiAgICAgICAgcHVibGljIGludCBmcm9tLCB0bzsKICAgICAgICBwdWJsaWMgbG9uZyBmbG93LCBjYXBhY2l0eTsKICAgICAgICBwdWJsaWMgRWRnZSByZXNpZHVhbDsKIAogICAgICAgIHB1YmxpYyBFZGdlKGludCBmLCBpbnQgdCwgbG9uZyBjYXApCiAgICAgICAgewogICAgICAgICAgICBmcm9tID0gZjsKICAgICAgICAgICAgdG8gPSB0OwogICAgICAgICAgICBjYXBhY2l0eSA9IGNhcDsKICAgICAgICB9CiAgICAgICAgcHVibGljIGxvbmcgY2FwYWNpdHlMZWZ0KCkKICAgICAgICB7CiAgICAgICAgICAgIHJldHVybiBjYXBhY2l0eS1mbG93OwogICAgICAgIH0KICAgICAgICBwdWJsaWMgdm9pZCBhdWdtZW50KGxvbmcgdmFsKQogICAgICAgIHsKICAgICAgICAgICAgZmxvdyArPSB2YWw7CiAgICAgICAgICAgIHJlc2lkdWFsLmZsb3cgLT0gdmFsOwogICAgICAgIH0KICAgIH0KfQoKY2xhc3MgRmFzdFJlYWRlcgp7CiAgICBCdWZmZXJlZFJlYWRlciBicjsKICAgIFN0cmluZ1Rva2VuaXplciBzdDsKCiAgICBwdWJsaWMgRmFzdFJlYWRlcigpCiAgICB7CiAgICAgICAgYnIgPSBuZXcgQnVmZmVyZWRSZWFkZXIobmV3IElucHV0U3RyZWFtUmVhZGVyKFN5c3RlbS5pbikpOwogICAgfQoKICAgIFN0cmluZyBuZXh0KCkKICAgIHsKICAgICAgICB3aGlsZSAoc3QgPT0gbnVsbCB8fCAhc3QuaGFzTW9yZUVsZW1lbnRzKCkpCiAgICAgICAgewogICAgICAgICAgICB0cnkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgc3QgPSBuZXcgU3RyaW5nVG9rZW5pemVyKGJyLnJlYWRMaW5lKCkpOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGNhdGNoIChJT0V4Y2VwdGlvbiAgZSkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgZS5wcmludFN0YWNrVHJhY2UoKTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICByZXR1cm4gc3QubmV4dFRva2VuKCk7CiAgICB9CgogICAgaW50IG5leHRJbnQoKQogICAgewogICAgICAgIHJldHVybiBJbnRlZ2VyLnBhcnNlSW50KG5leHQoKSk7CiAgICB9CgogICAgbG9uZyBuZXh0TG9uZygpCiAgICB7CiAgICAgICAgcmV0dXJuIExvbmcucGFyc2VMb25nKG5leHQoKSk7CiAgICB9CgogICAgZG91YmxlIG5leHREb3VibGUoKQogICAgewogICAgICAgIHJldHVybiBEb3VibGUucGFyc2VEb3VibGUobmV4dCgpKTsKICAgIH0KCiAgICBTdHJpbmcgbmV4dExpbmUoKQogICAgewogICAgICAgIFN0cmluZyBzdHIgPSAiIjsKICAgICAgICB0cnkKICAgICAgICB7CiAgICAgICAgICAgIHN0ciA9IGJyLnJlYWRMaW5lKCk7CiAgICAgICAgfQogICAgICAgIGNhdGNoIChJT0V4Y2VwdGlvbiBlKQogICAgICAgIHsKICAgICAgICAgICAgZS5wcmludFN0YWNrVHJhY2UoKTsKICAgICAgICB9CiAgICAgICAgcmV0dXJuIHN0cjsKICAgIH0KfQ==