#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("inline")
#include<bits/stdc++.h>
using namespace std;
template < class T> struct cLtraits_identity{
using type = T;
}
;
template < class T> using cLtraits_try_make_unsigned =
typename conditional<
is_integral< T> :: value ,
make_unsigned< T> ,
cLtraits_identity< T>
> :: type ;
void * wmem;
char memarr[ 96000000 ] ;
template < class S, class T> inline S chmin( S & a, T b) {
if ( a> b) {
a= b;
}
return a;
}
template < class S, class T> inline S chmax( S & a, T b) {
if ( a< b) {
a= b;
}
return a;
}
template < class S, class T> inline S divup_L( S a, T b) {
return ( a+ b- 1 ) / b;
}
template < class T> inline void walloc1d( T ** arr, int x, void ** mem = & wmem) {
static int skip[ 16 ] = { 0 , 15 , 14 , 13 , 12 , 11 , 10 , 9 , 8 , 7 , 6 , 5 , 4 , 3 , 2 , 1 } ;
( * mem) = ( void * ) ( ( ( char * ) ( * mem) ) + skip[ ( ( unsigned long long ) ( * mem) ) & 15 ] ) ;
( * arr) = ( T* ) ( * mem) ;
( * mem) = ( ( * arr) + x) ;
}
template < class T> inline void walloc1d( T ** arr, int x1, int x2, void ** mem = & wmem) {
walloc1d( arr, x2- x1, mem) ;
( * arr) - = x1;
}
inline int Ilog2_f_L( const int n) {
int res;
if ( n <= 0 ) {
return - 1 ;
}
res = sizeof ( int ) * 8 - __builtin_clz( n) - 1 ;
return res;
}
inline int Ilog2_f_L( const long long n) {
int res;
if ( n <= 0 ) {
return - 1 ;
}
res = sizeof ( long long ) * 8 - __builtin_clzll( n) - 1 ;
return res;
}
template < class T1> void sortI( int N, T1 a[ ] , void * mem = wmem) {
sort( a, a+ N) ;
}
template < class T1, class T2> void sortI( int N, T1 a[ ] , T2 b[ ] , void * mem = wmem) {
int i;
pair< T1, T2> * arr;
walloc1d( & arr, N, & mem) ;
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
arr[ i] .first = a[ i] ;
arr[ i] .second = b[ i] ;
}
sort( arr, arr+ N) ;
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
a[ i] = arr[ i] .first ;
b[ i] = arr[ i] .second ;
}
}
template < class T1, class T2, class T3> void sortI( int N, T1 a[ ] , T2 b[ ] , T3 c[ ] , void * mem = wmem) {
int i;
pair< T1, pair< T2, T3> > * arr;
walloc1d( & arr, N, & mem) ;
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
arr[ i] .first = a[ i] ;
arr[ i] .second .first = b[ i] ;
arr[ i] .second .second = c[ i] ;
}
sort( arr, arr+ N) ;
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
a[ i] = arr[ i] .first ;
b[ i] = arr[ i] .second .first ;
c[ i] = arr[ i] .second .second ;
}
}
template < class T1, class T2, class T3, class T4> void sortI( int N, T1 a[ ] , T2 b[ ] , T3 c[ ] , T4 d[ ] , void * mem = wmem) {
int i;
pair< pair< T1, T2> , pair< T3, T4> > * arr;
walloc1d( & arr, N, & mem) ;
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
arr[ i] .first .first = a[ i] ;
arr[ i] .first .second = b[ i] ;
arr[ i] .second .first = c[ i] ;
arr[ i] .second .second = d[ i] ;
}
sort( arr, arr+ N) ;
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
a[ i] = arr[ i] .first .first ;
b[ i] = arr[ i] .first .second ;
c[ i] = arr[ i] .second .first ;
d[ i] = arr[ i] .second .second ;
}
}
template < class T> inline int sort_helper_getbit( T A[ ] ) {
return - 1 ;
}
template <> inline int sort_helper_getbit( int A[ ] ) {
return sizeof ( int ) * 8 ;
}
template <> inline int sort_helper_getbit( unsigned A[ ] ) {
return sizeof ( unsigned ) * 8 ;
}
template <> inline int sort_helper_getbit( long long A[ ] ) {
return sizeof ( long long ) * 8 ;
}
template <> inline int sort_helper_getbit( unsigned long long A[ ] ) {
return sizeof ( unsigned long long ) * 8 ;
}
template <> inline int sort_helper_getbit( char A[ ] ) {
return sizeof ( char ) * 8 ;
}
template < class T> void sortA_1_int_L( int N, T A[ ] , void * mem = wmem) {
int i;
int j;
int k;
int b;
int s;
int ok;
ok = 1 ;
for ( i= ( 1 ) ; i< ( N) ; i++ ) {
if ( A[ i- 1 ] > A[ i] ) {
ok = 0 ;
break ;
}
}
if ( ok) {
return ;
}
if ( N < 128 ) {
sort( A,A+ N) ;
return ;
}
b = sort_helper_getbit( A) ;
if ( b== - 1 ) {
sort( A,A+ N) ;
return ;
}
T mn;
T mx;
mn = mx = A[ 0 ] ;
for ( i= ( 1 ) ; i< ( N) ; i++ ) {
chmin( mn, A[ i] ) ;
}
for ( i= ( 1 ) ; i< ( N) ; i++ ) {
chmax( mx, A[ i] ) ;
}
ok = 1 ;
if ( mn < 0 && mx > 0 && ( mn < - N || mx > N) ) {
ok = 0 ;
}
if ( ok && mx - mn > N) {
ok = 0 ;
}
if ( ok) {
int * tmp;
walloc1d( & tmp, mx- mn+ 1 , & mem) ;
for ( i= ( 0 ) ; i< ( mx- mn+ 1 ) ; i++ ) {
tmp[ i] = 0 ;
}
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
tmp[ A[ i] - mn] ++ ;
}
k = 0 ;
for ( i= ( 0 ) ; i< ( mx- mn+ 1 ) ; i++ ) {
while ( tmp[ i] > 0 ) {
tmp[ i] -- ;
A[ k++ ] = i+ mn;
}
}
return ;
}
{
typename make_unsigned< T> :: type * t[ 2 ] ;
typename make_unsigned< T> :: type mask;
typename make_unsigned< T> :: type cur;
typename make_unsigned< T> :: type one = 1 ;
T tone = 1 ;
int * pos;
int nn = 0 ;
int ss;
s = Ilog2_f_L( N) ;
if ( s > 8 ) {
s = ( 8 + ( s- 7 ) / 2 ) ;
}
ss = 1 ;
for ( ;; ) {
if ( ss >= b) {
break ;
}
if ( mx >= 0 && ( tone << ( ss- 1 ) ) < mx ) {
ss++ ;
continue ;
}
if ( mn < 0 && - ( tone << ( ss- 1 ) ) >= mn ) {
ss++ ;
continue ;
}
break ;
}
k = ( divup_L( ss,s) ) ;
s = ( divup_L( ss,k) ) ;
mask = 0 ;
for ( i= ( 0 ) ; i< ( b) ; i++ ) {
if ( i < s* k) {
mask | = one << i;
}
}
t[ 0 ] = ( typename make_unsigned< T> :: type * ) A;
walloc1d( & t[ 1 ] , N, & mem) ;
walloc1d( & pos, ( 1 << s) + 1 , & mem) ;
for ( j= ( 0 ) ; j< ( k) ; j++ ) {
cur = 0 ;
for ( i= ( 0 ) ; i< ( b) ; i++ ) {
if ( s* j <= i && i < s* ( j+ 1 ) && i < b) {
cur | = one << i;
}
}
for ( i= ( 0 ) ; i< ( ( 1 << s) + 1 ) ; i++ ) {
pos[ i] = 0 ;
}
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
pos[ ( ( t[ nn] [ i] & cur) >> ( s* j) ) + 1 ] ++ ;
}
for ( i= ( 0 ) ; i< ( ( 1 << s) ) ; i++ ) {
pos[ i+ 1 ] + = pos[ i] ;
}
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
t[ nn^ 1 ] [ pos[ ( t[ nn] [ i] & cur) >> ( s* j) ] ++ ] = t[ nn] [ i] ;
}
nn ^ = 1 ;
mask ^ = cur;
}
if ( mn < 0 && mx >= 0 ) {
k = 0 ;
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
if ( A[ i] < 0 ) {
k++ ;
}
}
for ( i= ( 0 ) ; i< ( k) ; i++ ) {
t[ nn^ 1 ] [ i] = t[ nn] [ N- k+ i] ;
}
for ( i= ( k) ; i< ( N) ; i++ ) {
t[ nn^ 1 ] [ i] = t[ nn] [ i- k] ;
}
nn ^ = 1 ;
}
if ( nn== 1 ) {
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
t[ 0 ] [ i] = t[ 1 ] [ i] ;
}
}
return ;
}
sort( A, A+ N) ;
}
template < class T> void sortA_1_nonint_L( int N, T A[ ] , void * mem = wmem) {
sort( A,A+ N) ;
}
template < class T> void sortA_1_call_L( int N, T A[ ] , void * mem = wmem) {
sortA_1_nonint_L( N, A, mem) ;
}
template <> void sortA_1_call_L( int N, int A[ ] , void * mem) {
sortA_1_int_L( N, A, mem) ;
}
template <> void sortA_1_call_L( int N, unsigned A[ ] , void * mem) {
sortA_1_int_L( N, A, mem) ;
}
template <> void sortA_1_call_L( int N, long long A[ ] , void * mem) {
sortA_1_int_L( N, A, mem) ;
}
template <> void sortA_1_call_L( int N, unsigned long long A[ ] , void * mem) {
sortA_1_int_L( N, A, mem) ;
}
template <> void sortA_1_call_L( int N, char A[ ] , void * mem) {
sortA_1_int_L( N, A, mem) ;
}
template < class T1> void sortA( int N, T1 a[ ] , void * mem = wmem) {
sortA_1_call_L( N, a, mem) ;
}
template < class T1, class T2> void sortA_2_int_L( int N, T1 A[ ] , T2 B[ ] , void * mem = wmem) {
int i;
int b_a;
int b_b;
int s1;
int s2;
int so2;
T1 mn1;
T1 mx1;
T2 mn2;
T2 mx2;
typename cLtraits_try_make_unsigned< T1> :: type r1;
typename cLtraits_try_make_unsigned< T2> :: type r2;
so2 = 1 ;
for ( i= ( 1 ) ; i< ( N) ; i++ ) {
if ( A[ i- 1 ] > A[ i] || ( A[ i- 1 ] == A[ i] && B[ i- 1 ] > B[ i] ) ) {
so2 = 0 ;
break ;
}
}
if ( so2) {
return ;
}
so2 = 1 ;
for ( i= ( 1 ) ; i< ( N) ; i++ ) {
if ( A[ i- 1 ] > A[ i] ) {
so2 = 0 ;
break ;
}
}
if ( so2== 1 ) {
int k = 0 ;
for ( i= ( 1 ) ; i< ( N) ; i++ ) {
if ( A[ i] ! = A[ i- 1 ] ) {
sortA_1_call_L( i- k, B+ k, mem) ;
k = i;
}
}
sortA_1_call_L( N- k, B+ k, mem) ;
return ;
}
if ( N < 128 ) {
sortI( N,A,B,mem) ;
return ;
}
b_a = sort_helper_getbit( A) ;
b_b = sort_helper_getbit( B) ;
if ( b_a == - 1 || b_b == - 1 ) {
sortI( N,A,B,mem) ;
return ;
}
mn1 = mx1 = A[ 0 ] ;
for ( i= ( 1 ) ; i< ( N) ; i++ ) {
chmin( mn1, A[ i] ) ;
}
for ( i= ( 1 ) ; i< ( N) ; i++ ) {
chmax( mx1, A[ i] ) ;
}
mn2 = mx2 = B[ 0 ] ;
for ( i= ( 1 ) ; i< ( N) ; i++ ) {
chmin( mn2, B[ i] ) ;
}
for ( i= ( 1 ) ; i< ( N) ; i++ ) {
chmax( mx2, B[ i] ) ;
}
if ( mn1 < - 4611686016279904256LL || mn2 < - 4611686016279904256LL || mx1 > 4611686016279904256LL || mx2 > 4611686016279904256LL || mx1- mn1 > 4611686016279904256LL || mx2- mn2 > 4611686016279904256LL) {
sortI( N,A,B,mem) ;
return ;
}
r1 = ( typename cLtraits_try_make_unsigned< T1> :: type ) ( mx1) - ( typename cLtraits_try_make_unsigned< T1> :: type ) ( mn1) ;
r2 = ( typename cLtraits_try_make_unsigned< T2> :: type ) ( mx2) - ( typename cLtraits_try_make_unsigned< T2> :: type ) ( mn2) ;
if ( r1 == 0 ) {
sortA_1_call_L( N, B, mem) ;
return ;
}
if ( r2 == 0 ) {
sortA_1_call_L( N, A, mem) ;
return ;
}
if ( r1 <= N) {
so2 = 1 ;
for ( i= ( 1 ) ; i< ( N) ; i++ ) {
if ( B[ i- 1 ] > B[ i] ) {
so2 = 0 ;
break ;
}
}
if ( so2 == 1 ) {
T1* aa;
T2* bb;
int * pos;
int k;
walloc1d( & aa,N,& mem) ;
walloc1d( & bb,N,& mem) ;
walloc1d( & pos,r1+ 2 ,& mem) ;
for ( i= ( 0 ) ; i< ( r1+ 2 ) ; i++ ) {
pos[ i] = 0 ;
}
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
aa[ i] = A[ i] ;
}
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
bb[ i] = B[ i] ;
}
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
pos[ ( typename cLtraits_try_make_unsigned< T1> :: type ) ( ( typename cLtraits_try_make_unsigned< T1> :: type ) aa[ i] - ( typename cLtraits_try_make_unsigned< T1> :: type ) mn1) + 1 ] ++ ;
}
for ( i= ( 1 ) ; i< ( r1+ 2 ) ; i++ ) {
pos[ i] + = pos[ i- 1 ] ;
}
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
k = pos[ ( typename cLtraits_try_make_unsigned< T1> :: type ) ( ( typename cLtraits_try_make_unsigned< T1> :: type ) aa[ i] - ( typename cLtraits_try_make_unsigned< T1> :: type ) mn1) + 0 ] ++ ;
A[ k] = aa[ i] ;
B[ k] = bb[ i] ;
}
return ;
}
}
s1 = s2 = 1 ;
while ( s1 < 64 && r1 >= ( 1ULL<< s1) ) {
s1++ ;
}
while ( s2 < 64 && r2 >= ( 1ULL<< s2) ) {
s2++ ;
}
if ( s1 + s2 <= 32 ) {
unsigned * tmp;
walloc1d( & tmp,N,& mem) ;
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
tmp[ i] = ( ( ( unsigned ) ( ( int ) A[ i] - ( int ) mn1) ) << s2) | ( ( unsigned ) ( ( int ) B[ i] - ( int ) mn2) ) ;
}
sortA_1_call_L( N, tmp, mem) ;
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
A[ i] = ( ( int ) ( tmp[ i] >> s2) ) + ( ( int ) mn1) ;
B[ i] = ( ( int ) ( tmp[ i] & ( ( 1U<< s2) - 1 ) ) ) + ( ( int ) mn2) ;
}
return ;
}
if ( s1 + s2 <= 64 ) {
unsigned long long * tmp;
walloc1d( & tmp,N,& mem) ;
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
tmp[ i] = ( ( ( unsigned long long ) ( ( long long ) A[ i] - ( long long ) mn1) ) << s2) | ( ( unsigned long long ) ( ( long long ) B[ i] - ( long long ) mn2) ) ;
}
sortA_1_call_L( N, tmp, mem) ;
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
A[ i] = ( ( long long ) ( tmp[ i] >> s2) ) + ( ( long long ) mn1) ;
B[ i] = ( ( long long ) ( tmp[ i] & ( ( 1ULL<< s2) - 1 ) ) ) + ( ( long long ) mn2) ;
}
return ;
}
sortI( N,A,B,mem) ;
}
template < class T1, class T2> void sortA_2_nonint_L( int N, T1 A[ ] , T2 B[ ] , void * mem = wmem) {
sortI( N,A,B,mem) ;
}
template < class T1, class T2> void sortA_2_call_L( int N, T1 A[ ] , T2 B[ ] , void * mem = wmem) {
sortA_2_nonint_L( N, A, B, mem) ;
}
template < class T2> void sortA_2_call_L( int N, int A[ ] , T2 B[ ] , void * mem) {
sortA_2_int_L( N, A, B, mem) ;
}
template < class T2> void sortA_2_call_L( int N, unsigned A[ ] , T2 B[ ] , void * mem) {
sortA_2_int_L( N, A, B, mem) ;
}
template < class T2> void sortA_2_call_L( int N, long long A[ ] , T2 B[ ] , void * mem) {
sortA_2_int_L( N, A, B, mem) ;
}
template < class T2> void sortA_2_call_L( int N, unsigned long long A[ ] , T2 B[ ] , void * mem) {
sortA_2_int_L( N, A, B, mem) ;
}
template < class T2> void sortA_2_call_L( int N, char A[ ] , T2 B[ ] , void * mem) {
sortA_2_int_L( N, A, B, mem) ;
}
template < class T1, class T2> void sortA( int N, T1 a[ ] , T2 b[ ] , void * mem = wmem) {
sortA_2_call_L( N, a, b, mem) ;
}
template < class T1, class T2, class T3> void sortA( int N, T1 a[ ] , T2 b[ ] , T3 c[ ] , void * mem = wmem) {
int i;
pair< T1, pair< T2, T3> > * arr;
walloc1d( & arr, N, & mem) ;
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
arr[ i] .first = a[ i] ;
arr[ i] .second .first = b[ i] ;
arr[ i] .second .second = c[ i] ;
}
sort( arr, arr+ N) ;
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
a[ i] = arr[ i] .first ;
b[ i] = arr[ i] .second .first ;
c[ i] = arr[ i] .second .second ;
}
}
template < class T1, class T2, class T3, class T4> void sortA( int N, T1 a[ ] , T2 b[ ] , T3 c[ ] , T4 d[ ] , void * mem = wmem) {
int i;
pair< pair< T1, T2> , pair< T3, T4> > * arr;
walloc1d( & arr, N, & mem) ;
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
arr[ i] .first .first = a[ i] ;
arr[ i] .first .second = b[ i] ;
arr[ i] .second .first = c[ i] ;
arr[ i] .second .second = d[ i] ;
}
sort( arr, arr+ N) ;
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
a[ i] = arr[ i] .first .first ;
b[ i] = arr[ i] .first .second ;
c[ i] = arr[ i] .second .first ;
d[ i] = arr[ i] .second .second ;
}
}
template < class T> void Unique( int & N, T A[ ] , int sorted= 0 , void * mwm = wmem) {
int i;
int k;
if ( ! sorted) {
sortA( N, A) ;
}
k = 0 ;
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
if ( k== 0 || A[ k- 1 ] ! = A[ i] ) {
A[ k++ ] = A[ i] ;
}
}
N = k;
}
template < class T, class S> void Unique( int & N, T A[ ] , S B[ ] , int sorted= 0 , void * mem = wmem) {
int i;
int k = 0 ;
if ( ! sorted) {
sortA( N, A, B, mem) ;
}
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
if ( ! k || A[ k- 1 ] ! = A[ i] ) {
A[ k] = A[ i] ;
B[ k] = B[ i] ;
k++ ;
}
else {
B[ k- 1 ] + = B[ i] ;
}
}
N= k;
}
#define main dummy_main
int main( ) {
wmem = memarr;
return 0 ;
}
#undef main
int N;
int A[ 1000000 ] ;
int B[ 1000000 ] ;
long long ok[ 1000000 ] ;
long long val[ 1000000 ] ;
long long x[ 1000000 ] ;
long long y[ 1000000 ] ;
class Solution{
public :
int minGroupsForValidAssignment( vector< int > & nums) {
dummy_main( ) ;
int i;
int j;
int k;
int M = nums.size ( ) ;
long long res = 4611686016279904256LL;
N = nums.size ( ) ;
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
A[ i] = nums[ i] ;
B[ i] = 1 ;
}
Unique( N, A, B) ;
for ( i= ( 0 ) ; i< ( M+ 1 ) ; i++ ) {
ok[ i] = val[ i] = 0 ;
}
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
for ( j= ( 0 ) ; j< ( B[ i] + 1 ) ; j++ ) {
x[ j] = 0 ;
y[ j] = 1073709056 ;
}
for ( j= ( 1 ) ; j< ( B[ i] + 1 ) ; j++ ) {
k = B[ i] / j;
x[ k] = 1 ;
chmin( y[ k] , j) ;
if ( B[ i] % j== 0 ) {
x[ k- 1 ] = 1 ;
chmin( y[ k- 1 ] , j) ;
}
}
for ( j= ( 0 ) ; j< ( B[ i] + 1 ) ; j++ ) {
ok[ j] + = x[ j] ;
val[ j] + = y[ j] ;
}
}
for ( i= ( 1 ) ; i< ( M+ 1 ) ; i++ ) {
if ( ok[ i] == N) {
chmin( res, val[ i] ) ;
}
}
return res;
}
}
;
// cLay version 20231031-1
// --- original code ---
// #define main dummy_main
// {}
// #undef main
//
// int N, A[1d6], B[];
// ll ok[], val[], x[], y[];
//
// class Solution {
// public:
// int minGroupsForValidAssignment(VI &nums) {
// dummy_main();
// int i, j, k, M = nums.size();
// ll res = ll_inf;
// N = nums.size();
// rep(i,N) A[i] = nums[i], B[i] = 1;
// Unique(N, A, B);
//
// rep(i,M+1) ok[i] = val[i] = 0;
// rep(i,N){
// rep(j,B[i]+1) x[j] = 0, y[j] = int_inf;
// rep(j,1,B[i]+1){
// k = B[i] / j;
// x[k] = 1;
// y[k] <?= j;
// if(B[i]%j==0) x[k-1] = 1, y[k-1] <?= j;
// }
// rep(j,B[i]+1) ok[j] += x[j], val[j] += y[j];
// }
//
// rep(i,1,M+1) if(ok[i]==N) res <?= val[i];
// return res;
// }
// };
I3ByYWdtYSBHQ0Mgb3B0aW1pemUoIk9mYXN0IikKI3ByYWdtYSBHQ0Mgb3B0aW1pemUoInVucm9sbC1sb29wcyIpCiNwcmFnbWEgR0NDIG9wdGltaXplKCJpbmxpbmUiKQojaW5jbHVkZTxiaXRzL3N0ZGMrKy5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwp0ZW1wbGF0ZTxjbGFzcyBUPiBzdHJ1Y3QgY0x0cmFpdHNfaWRlbnRpdHl7CiAgdXNpbmcgdHlwZSA9IFQ7Cn0KOwp0ZW1wbGF0ZTxjbGFzcyBUPiB1c2luZyBjTHRyYWl0c190cnlfbWFrZV91bnNpZ25lZCA9CiAgdHlwZW5hbWUgY29uZGl0aW9uYWw8CiAgICBpc19pbnRlZ3JhbDxUPjo6dmFsdWUsCiAgICBtYWtlX3Vuc2lnbmVkPFQ+LAogICAgY0x0cmFpdHNfaWRlbnRpdHk8VD4KICAgID46OnR5cGU7CnZvaWQqd21lbTsKY2hhciBtZW1hcnJbOTYwMDAwMDBdOwp0ZW1wbGF0ZTxjbGFzcyBTLCBjbGFzcyBUPiBpbmxpbmUgUyBjaG1pbihTICZhLCBUIGIpewogIGlmKGE+Yil7CiAgICBhPWI7CiAgfQogIHJldHVybiBhOwp9CnRlbXBsYXRlPGNsYXNzIFMsIGNsYXNzIFQ+IGlubGluZSBTIGNobWF4KFMgJmEsIFQgYil7CiAgaWYoYTxiKXsKICAgIGE9YjsKICB9CiAgcmV0dXJuIGE7Cn0KdGVtcGxhdGU8Y2xhc3MgUywgY2xhc3MgVD4gaW5saW5lIFMgZGl2dXBfTChTIGEsIFQgYil7CiAgcmV0dXJuIChhK2ItMSkvYjsKfQp0ZW1wbGF0ZTxjbGFzcyBUPiBpbmxpbmUgdm9pZCB3YWxsb2MxZChUICoqYXJyLCBpbnQgeCwgdm9pZCAqKm1lbSA9ICZ3bWVtKXsKICBzdGF0aWMgaW50IHNraXBbMTZdID0gezAsIDE1LCAxNCwgMTMsIDEyLCAxMSwgMTAsIDksIDgsIDcsIDYsIDUsIDQsIDMsIDIsIDF9OwogICgqbWVtKSA9ICh2b2lkKikoICgoY2hhciopKCptZW0pKSArIHNraXBbKCh1bnNpZ25lZCBsb25nIGxvbmcpKCptZW0pKSAmIDE1XSApOwogICgqYXJyKT0oVCopKCptZW0pOwogICgqbWVtKT0oKCphcnIpK3gpOwp9CnRlbXBsYXRlPGNsYXNzIFQ+IGlubGluZSB2b2lkIHdhbGxvYzFkKFQgKiphcnIsIGludCB4MSwgaW50IHgyLCB2b2lkICoqbWVtID0gJndtZW0pewogIHdhbGxvYzFkKGFyciwgeDIteDEsIG1lbSk7CiAgKCphcnIpIC09IHgxOwp9CmlubGluZSBpbnQgSWxvZzJfZl9MKGNvbnN0IGludCBuKXsKICBpbnQgcmVzOwogIGlmKG4gPD0gMCl7CiAgICByZXR1cm4gLTE7CiAgfQogIHJlcyA9IHNpemVvZihpbnQpICogOCAtIF9fYnVpbHRpbl9jbHoobikgLSAxOwogIHJldHVybiByZXM7Cn0KaW5saW5lIGludCBJbG9nMl9mX0woY29uc3QgbG9uZyBsb25nIG4pewogIGludCByZXM7CiAgaWYobiA8PSAwKXsKICAgIHJldHVybiAtMTsKICB9CiAgcmVzID0gc2l6ZW9mKGxvbmcgbG9uZykgKiA4IC0gX19idWlsdGluX2NsemxsKG4pIC0gMTsKICByZXR1cm4gcmVzOwp9CnRlbXBsYXRlPGNsYXNzIFQxPiB2b2lkIHNvcnRJKGludCBOLCBUMSBhW10sIHZvaWQgKm1lbSA9IHdtZW0pewogIHNvcnQoYSwgYStOKTsKfQp0ZW1wbGF0ZTxjbGFzcyBUMSwgY2xhc3MgVDI+IHZvaWQgc29ydEkoaW50IE4sIFQxIGFbXSwgVDIgYltdLCB2b2lkICptZW0gPSB3bWVtKXsKICBpbnQgaTsKICBwYWlyPFQxLCBUMj4qYXJyOwogIHdhbGxvYzFkKCZhcnIsIE4sICZtZW0pOwogIGZvcihpPSgwKTtpPChOKTtpKyspewogICAgYXJyW2ldLmZpcnN0ID0gYVtpXTsKICAgIGFycltpXS5zZWNvbmQgPSBiW2ldOwogIH0KICBzb3J0KGFyciwgYXJyK04pOwogIGZvcihpPSgwKTtpPChOKTtpKyspewogICAgYVtpXSA9IGFycltpXS5maXJzdDsKICAgIGJbaV0gPSBhcnJbaV0uc2Vjb25kOwogIH0KfQp0ZW1wbGF0ZTxjbGFzcyBUMSwgY2xhc3MgVDIsIGNsYXNzIFQzPiB2b2lkIHNvcnRJKGludCBOLCBUMSBhW10sIFQyIGJbXSwgVDMgY1tdLCB2b2lkICptZW0gPSB3bWVtKXsKICBpbnQgaTsKICBwYWlyPFQxLCBwYWlyPFQyLCBUMz4gPiphcnI7CiAgd2FsbG9jMWQoJmFyciwgTiwgJm1lbSk7CiAgZm9yKGk9KDApO2k8KE4pO2krKyl7CiAgICBhcnJbaV0uZmlyc3QgPSBhW2ldOwogICAgYXJyW2ldLnNlY29uZC5maXJzdCA9IGJbaV07CiAgICBhcnJbaV0uc2Vjb25kLnNlY29uZCA9IGNbaV07CiAgfQogIHNvcnQoYXJyLCBhcnIrTik7CiAgZm9yKGk9KDApO2k8KE4pO2krKyl7CiAgICBhW2ldID0gYXJyW2ldLmZpcnN0OwogICAgYltpXSA9IGFycltpXS5zZWNvbmQuZmlyc3Q7CiAgICBjW2ldID0gYXJyW2ldLnNlY29uZC5zZWNvbmQ7CiAgfQp9CnRlbXBsYXRlPGNsYXNzIFQxLCBjbGFzcyBUMiwgY2xhc3MgVDMsIGNsYXNzIFQ0PiB2b2lkIHNvcnRJKGludCBOLCBUMSBhW10sIFQyIGJbXSwgVDMgY1tdLCBUNCBkW10sIHZvaWQgKm1lbSA9IHdtZW0pewogIGludCBpOwogIHBhaXI8cGFpcjxUMSwgVDI+LCBwYWlyPFQzLCBUND4gPiphcnI7CiAgd2FsbG9jMWQoJmFyciwgTiwgJm1lbSk7CiAgZm9yKGk9KDApO2k8KE4pO2krKyl7CiAgICBhcnJbaV0uZmlyc3QuZmlyc3QgPSBhW2ldOwogICAgYXJyW2ldLmZpcnN0LnNlY29uZCA9IGJbaV07CiAgICBhcnJbaV0uc2Vjb25kLmZpcnN0ID0gY1tpXTsKICAgIGFycltpXS5zZWNvbmQuc2Vjb25kID0gZFtpXTsKICB9CiAgc29ydChhcnIsIGFycitOKTsKICBmb3IoaT0oMCk7aTwoTik7aSsrKXsKICAgIGFbaV0gPSBhcnJbaV0uZmlyc3QuZmlyc3Q7CiAgICBiW2ldID0gYXJyW2ldLmZpcnN0LnNlY29uZDsKICAgIGNbaV0gPSBhcnJbaV0uc2Vjb25kLmZpcnN0OwogICAgZFtpXSA9IGFycltpXS5zZWNvbmQuc2Vjb25kOwogIH0KfQp0ZW1wbGF0ZTxjbGFzcyBUPiBpbmxpbmUgaW50IHNvcnRfaGVscGVyX2dldGJpdChUIEFbXSl7CiAgcmV0dXJuIC0xOwp9CnRlbXBsYXRlPD4gaW5saW5lIGludCBzb3J0X2hlbHBlcl9nZXRiaXQoaW50IEFbXSl7CiAgcmV0dXJuIHNpemVvZihpbnQpKjg7Cn0KdGVtcGxhdGU8PiBpbmxpbmUgaW50IHNvcnRfaGVscGVyX2dldGJpdCh1bnNpZ25lZCBBW10pewogIHJldHVybiBzaXplb2YodW5zaWduZWQpKjg7Cn0KdGVtcGxhdGU8PiBpbmxpbmUgaW50IHNvcnRfaGVscGVyX2dldGJpdChsb25nIGxvbmcgQVtdKXsKICByZXR1cm4gc2l6ZW9mKGxvbmcgbG9uZykqODsKfQp0ZW1wbGF0ZTw+IGlubGluZSBpbnQgc29ydF9oZWxwZXJfZ2V0Yml0KHVuc2lnbmVkIGxvbmcgbG9uZyBBW10pewogIHJldHVybiBzaXplb2YodW5zaWduZWQgbG9uZyBsb25nKSo4Owp9CnRlbXBsYXRlPD4gaW5saW5lIGludCBzb3J0X2hlbHBlcl9nZXRiaXQoY2hhciBBW10pewogIHJldHVybiBzaXplb2YoY2hhcikqODsKfQp0ZW1wbGF0ZTxjbGFzcyBUPiB2b2lkIHNvcnRBXzFfaW50X0woaW50IE4sIFQgQVtdLCB2b2lkICptZW0gPSB3bWVtKXsKICBpbnQgaTsKICBpbnQgajsKICBpbnQgazsKICBpbnQgYjsKICBpbnQgczsKICBpbnQgb2s7CiAgb2sgPSAxOwogIGZvcihpPSgxKTtpPChOKTtpKyspewogICAgaWYoQVtpLTFdID4gQVtpXSl7CiAgICAgIG9rID0gMDsKICAgICAgYnJlYWs7CiAgICB9CiAgfQogIGlmKG9rKXsKICAgIHJldHVybjsKICB9CiAgaWYoTiA8IDEyOCl7CiAgICBzb3J0KEEsQStOKTsKICAgIHJldHVybjsKICB9CiAgYiA9IHNvcnRfaGVscGVyX2dldGJpdChBKTsKICBpZihiPT0tMSl7CiAgICBzb3J0KEEsQStOKTsKICAgIHJldHVybjsKICB9CiAgVCBtbjsKICBUIG14OwogIG1uID0gbXggPSBBWzBdOwogIGZvcihpPSgxKTtpPChOKTtpKyspewogICAgY2htaW4obW4sIEFbaV0pOwogIH0KICBmb3IoaT0oMSk7aTwoTik7aSsrKXsKICAgIGNobWF4KG14LCBBW2ldKTsKICB9CiAgb2sgPSAxOwogIGlmKG1uIDwgMCAmJiBteCA+IDAgJiYgKG1uIDwgLU4gfHwgbXggPiBOKSl7CiAgICBvayA9IDA7CiAgfQogIGlmKG9rICYmIG14IC0gbW4gPiBOKXsKICAgIG9rID0gMDsKICB9CiAgaWYob2spewogICAgaW50KnRtcDsKICAgIHdhbGxvYzFkKCZ0bXAsIG14LW1uKzEsICZtZW0pOwogICAgZm9yKGk9KDApO2k8KG14LW1uKzEpO2krKyl7CiAgICAgIHRtcFtpXSA9IDA7CiAgICB9CiAgICBmb3IoaT0oMCk7aTwoTik7aSsrKXsKICAgICAgdG1wW0FbaV0tbW5dKys7CiAgICB9CiAgICBrID0gMDsKICAgIGZvcihpPSgwKTtpPChteC1tbisxKTtpKyspewogICAgICB3aGlsZSh0bXBbaV0gPiAwKXsKICAgICAgICB0bXBbaV0tLTsKICAgICAgICBBW2srK10gPSBpK21uOwogICAgICB9CiAgICB9CiAgICByZXR1cm47CiAgfQogIHsKICAgIHR5cGVuYW1lIG1ha2VfdW5zaWduZWQ8VD46OnR5cGUgKnRbMl07CiAgICB0eXBlbmFtZSBtYWtlX3Vuc2lnbmVkPFQ+Ojp0eXBlICBtYXNrOwogICAgdHlwZW5hbWUgbWFrZV91bnNpZ25lZDxUPjo6dHlwZSAgY3VyOwogICAgdHlwZW5hbWUgbWFrZV91bnNpZ25lZDxUPjo6dHlwZSAgb25lID0gMTsKICAgIFQgdG9uZSA9IDE7CiAgICBpbnQqcG9zOwogICAgaW50IG5uID0gMDsKICAgIGludCBzczsKICAgIHMgPUlsb2cyX2ZfTChOKTsKICAgIGlmKHMgPiA4KXsKICAgICAgcyA9ICg4ICsgKHMtNykvMik7CiAgICB9CiAgICBzcyA9IDE7CiAgICBmb3IoOzspewogICAgICBpZihzcyA+PSBiKXsKICAgICAgICBicmVhazsKICAgICAgfQogICAgICBpZiggbXggPj0gMCAmJiAodG9uZSA8PCAoc3MtMSkpIDwgbXggKXsKICAgICAgICBzcysrOwogICAgICAgIGNvbnRpbnVlOwogICAgICB9CiAgICAgIGlmKCBtbiA8IDAgJiYgLSh0b25lIDw8IChzcy0xKSkgPj0gbW4gKXsKICAgICAgICBzcysrOwogICAgICAgIGNvbnRpbnVlOwogICAgICB9CiAgICAgIGJyZWFrOwogICAgfQogICAgayA9KGRpdnVwX0woc3MscykpOwogICAgcyA9KGRpdnVwX0woc3MsaykpOwogICAgbWFzayA9IDA7CiAgICBmb3IoaT0oMCk7aTwoYik7aSsrKXsKICAgICAgaWYoaSA8IHMqayl7CiAgICAgICAgbWFzayB8PSBvbmUgPDwgaTsKICAgICAgfQogICAgfQogICAgdFswXSA9ICh0eXBlbmFtZSBtYWtlX3Vuc2lnbmVkPFQ+Ojp0eXBlICopIEE7CiAgICB3YWxsb2MxZCgmdFsxXSwgTiwgJm1lbSk7CiAgICB3YWxsb2MxZCgmcG9zLCAoMTw8cykrMSwgJm1lbSk7CiAgICBmb3Ioaj0oMCk7ajwoayk7aisrKXsKICAgICAgY3VyID0gMDsKICAgICAgZm9yKGk9KDApO2k8KGIpO2krKyl7CiAgICAgICAgaWYocypqIDw9IGkgJiYgaSA8IHMqKGorMSkgJiYgaSA8IGIpewogICAgICAgICAgY3VyIHw9IG9uZSA8PCBpOwogICAgICAgIH0KICAgICAgfQogICAgICBmb3IoaT0oMCk7aTwoKDE8PHMpKzEpO2krKyl7CiAgICAgICAgcG9zW2ldID0gMDsKICAgICAgfQogICAgICBmb3IoaT0oMCk7aTwoTik7aSsrKXsKICAgICAgICBwb3NbKCh0W25uXVtpXSZjdXIpPj4ocypqKSkrMV0rKzsKICAgICAgfQogICAgICBmb3IoaT0oMCk7aTwoKDE8PHMpKTtpKyspewogICAgICAgIHBvc1tpKzFdICs9IHBvc1tpXTsKICAgICAgfQogICAgICBmb3IoaT0oMCk7aTwoTik7aSsrKXsKICAgICAgICB0W25uXjFdW3Bvc1sodFtubl1baV0mY3VyKT4+KHMqaildKytdID0gdFtubl1baV07CiAgICAgIH0KICAgICAgbm4gXj0gMTsKICAgICAgbWFzayBePSBjdXI7CiAgICB9CiAgICBpZihtbiA8IDAgJiYgbXggPj0gMCl7CiAgICAgIGsgPSAwOwogICAgICBmb3IoaT0oMCk7aTwoTik7aSsrKXsKICAgICAgICBpZihBW2ldIDwgMCl7CiAgICAgICAgICBrKys7CiAgICAgICAgfQogICAgICB9CiAgICAgIGZvcihpPSgwKTtpPChrKTtpKyspewogICAgICAgIHRbbm5eMV1baV0gPSB0W25uXVtOLWsraV07CiAgICAgIH0KICAgICAgZm9yKGk9KGspO2k8KE4pO2krKyl7CiAgICAgICAgdFtubl4xXVtpXSA9IHRbbm5dW2kta107CiAgICAgIH0KICAgICAgbm4gXj0gMTsKICAgIH0KICAgIGlmKG5uPT0xKXsKICAgICAgZm9yKGk9KDApO2k8KE4pO2krKyl7CiAgICAgICAgdFswXVtpXSA9IHRbMV1baV07CiAgICAgIH0KICAgIH0KICAgIHJldHVybjsKICB9CiAgc29ydChBLCBBK04pOwp9CnRlbXBsYXRlPGNsYXNzIFQ+IHZvaWQgc29ydEFfMV9ub25pbnRfTChpbnQgTiwgVCBBW10sIHZvaWQgKm1lbSA9IHdtZW0pewogIHNvcnQoQSxBK04pOwp9CnRlbXBsYXRlPGNsYXNzIFQ+IHZvaWQgc29ydEFfMV9jYWxsX0woaW50IE4sIFQgQVtdLCB2b2lkICptZW0gPSB3bWVtKXsKICBzb3J0QV8xX25vbmludF9MKE4sIEEsIG1lbSk7Cn0KdGVtcGxhdGU8PiB2b2lkIHNvcnRBXzFfY2FsbF9MKGludCBOLCBpbnQgQVtdLCB2b2lkICptZW0pewogIHNvcnRBXzFfaW50X0woTiwgQSwgbWVtKTsKfQp0ZW1wbGF0ZTw+IHZvaWQgc29ydEFfMV9jYWxsX0woaW50IE4sIHVuc2lnbmVkIEFbXSwgdm9pZCAqbWVtKXsKICBzb3J0QV8xX2ludF9MKE4sIEEsIG1lbSk7Cn0KdGVtcGxhdGU8PiB2b2lkIHNvcnRBXzFfY2FsbF9MKGludCBOLCBsb25nIGxvbmcgQVtdLCB2b2lkICptZW0pewogIHNvcnRBXzFfaW50X0woTiwgQSwgbWVtKTsKfQp0ZW1wbGF0ZTw+IHZvaWQgc29ydEFfMV9jYWxsX0woaW50IE4sIHVuc2lnbmVkIGxvbmcgbG9uZyBBW10sIHZvaWQgKm1lbSl7CiAgc29ydEFfMV9pbnRfTChOLCBBLCBtZW0pOwp9CnRlbXBsYXRlPD4gdm9pZCBzb3J0QV8xX2NhbGxfTChpbnQgTiwgY2hhciBBW10sIHZvaWQgKm1lbSl7CiAgc29ydEFfMV9pbnRfTChOLCBBLCBtZW0pOwp9CnRlbXBsYXRlPGNsYXNzIFQxPiB2b2lkIHNvcnRBKGludCBOLCBUMSBhW10sIHZvaWQgKm1lbSA9IHdtZW0pewogIHNvcnRBXzFfY2FsbF9MKE4sIGEsIG1lbSk7Cn0KdGVtcGxhdGU8Y2xhc3MgVDEsIGNsYXNzIFQyPiB2b2lkIHNvcnRBXzJfaW50X0woaW50IE4sIFQxIEFbXSwgVDIgQltdLCB2b2lkICptZW0gPSB3bWVtKXsKICBpbnQgaTsKICBpbnQgYl9hOwogIGludCBiX2I7CiAgaW50IHMxOwogIGludCBzMjsKICBpbnQgc28yOwogIFQxIG1uMTsKICBUMSBteDE7CiAgVDIgbW4yOwogIFQyIG14MjsKICB0eXBlbmFtZSBjTHRyYWl0c190cnlfbWFrZV91bnNpZ25lZDxUMT46OnR5cGUgcjE7CiAgdHlwZW5hbWUgY0x0cmFpdHNfdHJ5X21ha2VfdW5zaWduZWQ8VDI+Ojp0eXBlIHIyOwogIHNvMiA9IDE7CiAgZm9yKGk9KDEpO2k8KE4pO2krKyl7CiAgICBpZihBW2ktMV0gPiBBW2ldIHx8IChBW2ktMV09PUFbaV0gJiYgQltpLTFdID4gQltpXSkpewogICAgICBzbzIgPSAwOwogICAgICBicmVhazsKICAgIH0KICB9CiAgaWYoc28yKXsKICAgIHJldHVybjsKICB9CiAgc28yID0gMTsKICBmb3IoaT0oMSk7aTwoTik7aSsrKXsKICAgIGlmKEFbaS0xXSA+IEFbaV0pewogICAgICBzbzIgPSAwOwogICAgICBicmVhazsKICAgIH0KICB9CiAgaWYoc28yPT0xKXsKICAgIGludCBrID0gMDsKICAgIGZvcihpPSgxKTtpPChOKTtpKyspewogICAgICBpZihBW2ldICE9IEFbaS0xXSl7CiAgICAgICAgc29ydEFfMV9jYWxsX0woaS1rLCBCK2ssIG1lbSk7CiAgICAgICAgayA9IGk7CiAgICAgIH0KICAgIH0KICAgIHNvcnRBXzFfY2FsbF9MKE4taywgQitrLCBtZW0pOwogICAgcmV0dXJuOwogIH0KICBpZihOIDwgMTI4KXsKICAgIHNvcnRJKE4sQSxCLG1lbSk7CiAgICByZXR1cm47CiAgfQogIGJfYSA9IHNvcnRfaGVscGVyX2dldGJpdChBKTsKICBiX2IgPSBzb3J0X2hlbHBlcl9nZXRiaXQoQik7CiAgaWYoYl9hID09IC0xIHx8IGJfYiA9PSAtMSl7CiAgICBzb3J0SShOLEEsQixtZW0pOwogICAgcmV0dXJuOwogIH0KICBtbjEgPSBteDEgPSBBWzBdOwogIGZvcihpPSgxKTtpPChOKTtpKyspewogICAgY2htaW4obW4xLCBBW2ldKTsKICB9CiAgZm9yKGk9KDEpO2k8KE4pO2krKyl7CiAgICBjaG1heChteDEsIEFbaV0pOwogIH0KICBtbjIgPSBteDIgPSBCWzBdOwogIGZvcihpPSgxKTtpPChOKTtpKyspewogICAgY2htaW4obW4yLCBCW2ldKTsKICB9CiAgZm9yKGk9KDEpO2k8KE4pO2krKyl7CiAgICBjaG1heChteDIsIEJbaV0pOwogIH0KICBpZihtbjEgPCAtNDYxMTY4NjAxNjI3OTkwNDI1NkxMIHx8IG1uMiA8IC00NjExNjg2MDE2Mjc5OTA0MjU2TEwgfHwgbXgxID4gNDYxMTY4NjAxNjI3OTkwNDI1NkxMIHx8IG14MiA+IDQ2MTE2ODYwMTYyNzk5MDQyNTZMTCB8fCBteDEtbW4xID4gNDYxMTY4NjAxNjI3OTkwNDI1NkxMIHx8IG14Mi1tbjIgPiA0NjExNjg2MDE2Mjc5OTA0MjU2TEwpewogICAgc29ydEkoTixBLEIsbWVtKTsKICAgIHJldHVybjsKICB9CiAgcjEgPSAodHlwZW5hbWUgY0x0cmFpdHNfdHJ5X21ha2VfdW5zaWduZWQ8VDE+Ojp0eXBlKShteDEpIC0gKHR5cGVuYW1lIGNMdHJhaXRzX3RyeV9tYWtlX3Vuc2lnbmVkPFQxPjo6dHlwZSkobW4xKTsKICByMiA9ICh0eXBlbmFtZSBjTHRyYWl0c190cnlfbWFrZV91bnNpZ25lZDxUMj46OnR5cGUpKG14MikgLSAodHlwZW5hbWUgY0x0cmFpdHNfdHJ5X21ha2VfdW5zaWduZWQ8VDI+Ojp0eXBlKShtbjIpOwogIGlmKHIxID09IDApewogICAgc29ydEFfMV9jYWxsX0woTiwgQiwgbWVtKTsKICAgIHJldHVybjsKICB9CiAgaWYocjIgPT0gMCl7CiAgICBzb3J0QV8xX2NhbGxfTChOLCBBLCBtZW0pOwogICAgcmV0dXJuOwogIH0KICBpZihyMSA8PSBOKXsKICAgIHNvMiA9IDE7CiAgICBmb3IoaT0oMSk7aTwoTik7aSsrKXsKICAgICAgaWYoQltpLTFdID4gQltpXSl7CiAgICAgICAgc28yID0gMDsKICAgICAgICBicmVhazsKICAgICAgfQogICAgfQogICAgaWYoc28yID09IDEpewogICAgICBUMSphYTsKICAgICAgVDIqYmI7CiAgICAgIGludCpwb3M7CiAgICAgIGludCBrOwogICAgICB3YWxsb2MxZCgmYWEsTiwmbWVtKTsKICAgICAgd2FsbG9jMWQoJmJiLE4sJm1lbSk7CiAgICAgIHdhbGxvYzFkKCZwb3MscjErMiwmbWVtKTsKICAgICAgZm9yKGk9KDApO2k8KHIxKzIpO2krKyl7CiAgICAgICAgcG9zW2ldID0gMDsKICAgICAgfQogICAgICBmb3IoaT0oMCk7aTwoTik7aSsrKXsKICAgICAgICBhYVtpXSA9IEFbaV07CiAgICAgIH0KICAgICAgZm9yKGk9KDApO2k8KE4pO2krKyl7CiAgICAgICAgYmJbaV0gPSBCW2ldOwogICAgICB9CiAgICAgIGZvcihpPSgwKTtpPChOKTtpKyspewogICAgICAgIHBvc1sodHlwZW5hbWUgY0x0cmFpdHNfdHJ5X21ha2VfdW5zaWduZWQ8VDE+Ojp0eXBlKSgodHlwZW5hbWUgY0x0cmFpdHNfdHJ5X21ha2VfdW5zaWduZWQ8VDE+Ojp0eXBlKWFhW2ldLSh0eXBlbmFtZSBjTHRyYWl0c190cnlfbWFrZV91bnNpZ25lZDxUMT46OnR5cGUpbW4xKSsxXSsrOwogICAgICB9CiAgICAgIGZvcihpPSgxKTtpPChyMSsyKTtpKyspewogICAgICAgIHBvc1tpXSArPSBwb3NbaS0xXTsKICAgICAgfQogICAgICBmb3IoaT0oMCk7aTwoTik7aSsrKXsKICAgICAgICBrID0gcG9zWyh0eXBlbmFtZSBjTHRyYWl0c190cnlfbWFrZV91bnNpZ25lZDxUMT46OnR5cGUpKCh0eXBlbmFtZSBjTHRyYWl0c190cnlfbWFrZV91bnNpZ25lZDxUMT46OnR5cGUpYWFbaV0tKHR5cGVuYW1lIGNMdHJhaXRzX3RyeV9tYWtlX3Vuc2lnbmVkPFQxPjo6dHlwZSltbjEpKzBdKys7CiAgICAgICAgQVtrXSA9IGFhW2ldOwogICAgICAgIEJba10gPSBiYltpXTsKICAgICAgfQogICAgICByZXR1cm47CiAgICB9CiAgfQogIHMxID0gczIgPSAxOwogIHdoaWxlKCBzMSA8IDY0ICYmIHIxID49ICgxVUxMPDxzMSkgKXsKICAgIHMxKys7CiAgfQogIHdoaWxlKCBzMiA8IDY0ICYmIHIyID49ICgxVUxMPDxzMikgKXsKICAgIHMyKys7CiAgfQogIGlmKHMxICsgczIgPD0gMzIpewogICAgdW5zaWduZWQqdG1wOwogICAgd2FsbG9jMWQoJnRtcCxOLCZtZW0pOwogICAgZm9yKGk9KDApO2k8KE4pO2krKyl7CiAgICAgIHRtcFtpXSA9ICgoKHVuc2lnbmVkKSgoaW50KUFbaV0tKGludCltbjEpKSA8PCBzMikgfCAoKHVuc2lnbmVkKSgoaW50KUJbaV0tKGludCltbjIpKTsKICAgIH0KICAgIHNvcnRBXzFfY2FsbF9MKE4sIHRtcCwgbWVtKTsKICAgIGZvcihpPSgwKTtpPChOKTtpKyspewogICAgICBBW2ldID0gKChpbnQpKHRtcFtpXSA+PiBzMikpICsgKChpbnQpbW4xKTsKICAgICAgQltpXSA9ICgoaW50KSh0bXBbaV0gJiAoKDFVPDxzMiktMSkpKSArICgoaW50KW1uMik7CiAgICB9CiAgICByZXR1cm47CiAgfQogIGlmKHMxICsgczIgPD0gNjQpewogICAgdW5zaWduZWQgbG9uZyBsb25nKnRtcDsKICAgIHdhbGxvYzFkKCZ0bXAsTiwmbWVtKTsKICAgIGZvcihpPSgwKTtpPChOKTtpKyspewogICAgICB0bXBbaV0gPSAoKCh1bnNpZ25lZCBsb25nIGxvbmcpKChsb25nIGxvbmcpQVtpXS0obG9uZyBsb25nKW1uMSkpIDw8IHMyKSB8ICgodW5zaWduZWQgbG9uZyBsb25nKSgobG9uZyBsb25nKUJbaV0tKGxvbmcgbG9uZyltbjIpKTsKICAgIH0KICAgIHNvcnRBXzFfY2FsbF9MKE4sIHRtcCwgbWVtKTsKICAgIGZvcihpPSgwKTtpPChOKTtpKyspewogICAgICBBW2ldID0gKChsb25nIGxvbmcpKHRtcFtpXSA+PiBzMikpICsgKChsb25nIGxvbmcpbW4xKTsKICAgICAgQltpXSA9ICgobG9uZyBsb25nKSh0bXBbaV0gJiAoKDFVTEw8PHMyKS0xKSkpICsgKChsb25nIGxvbmcpbW4yKTsKICAgIH0KICAgIHJldHVybjsKICB9CiAgc29ydEkoTixBLEIsbWVtKTsKfQp0ZW1wbGF0ZTxjbGFzcyBUMSwgY2xhc3MgVDI+IHZvaWQgc29ydEFfMl9ub25pbnRfTChpbnQgTiwgVDEgQVtdLCBUMiBCW10sIHZvaWQgKm1lbSA9IHdtZW0pewogIHNvcnRJKE4sQSxCLG1lbSk7Cn0KdGVtcGxhdGU8Y2xhc3MgVDEsIGNsYXNzIFQyPiB2b2lkIHNvcnRBXzJfY2FsbF9MKGludCBOLCBUMSBBW10sIFQyIEJbXSwgdm9pZCAqbWVtID0gd21lbSl7CiAgc29ydEFfMl9ub25pbnRfTChOLCBBLCBCLCBtZW0pOwp9CnRlbXBsYXRlPGNsYXNzIFQyPiB2b2lkIHNvcnRBXzJfY2FsbF9MKGludCBOLCBpbnQgQVtdLCBUMiBCW10sIHZvaWQgKm1lbSl7CiAgc29ydEFfMl9pbnRfTChOLCBBLCBCLCBtZW0pOwp9CnRlbXBsYXRlPGNsYXNzIFQyPiB2b2lkIHNvcnRBXzJfY2FsbF9MKGludCBOLCB1bnNpZ25lZCBBW10sIFQyIEJbXSwgdm9pZCAqbWVtKXsKICBzb3J0QV8yX2ludF9MKE4sIEEsIEIsIG1lbSk7Cn0KdGVtcGxhdGU8Y2xhc3MgVDI+IHZvaWQgc29ydEFfMl9jYWxsX0woaW50IE4sIGxvbmcgbG9uZyBBW10sIFQyIEJbXSwgdm9pZCAqbWVtKXsKICBzb3J0QV8yX2ludF9MKE4sIEEsIEIsIG1lbSk7Cn0KdGVtcGxhdGU8Y2xhc3MgVDI+IHZvaWQgc29ydEFfMl9jYWxsX0woaW50IE4sIHVuc2lnbmVkIGxvbmcgbG9uZyBBW10sIFQyIEJbXSwgdm9pZCAqbWVtKXsKICBzb3J0QV8yX2ludF9MKE4sIEEsIEIsIG1lbSk7Cn0KdGVtcGxhdGU8Y2xhc3MgVDI+IHZvaWQgc29ydEFfMl9jYWxsX0woaW50IE4sIGNoYXIgQVtdLCBUMiBCW10sIHZvaWQgKm1lbSl7CiAgc29ydEFfMl9pbnRfTChOLCBBLCBCLCBtZW0pOwp9CnRlbXBsYXRlPGNsYXNzIFQxLCBjbGFzcyBUMj4gdm9pZCBzb3J0QShpbnQgTiwgVDEgYVtdLCBUMiBiW10sIHZvaWQgKm1lbSA9IHdtZW0pewogIHNvcnRBXzJfY2FsbF9MKE4sIGEsIGIsIG1lbSk7Cn0KdGVtcGxhdGU8Y2xhc3MgVDEsIGNsYXNzIFQyLCBjbGFzcyBUMz4gdm9pZCBzb3J0QShpbnQgTiwgVDEgYVtdLCBUMiBiW10sIFQzIGNbXSwgdm9pZCAqbWVtID0gd21lbSl7CiAgaW50IGk7CiAgcGFpcjxUMSwgcGFpcjxUMiwgVDM+ID4qYXJyOwogIHdhbGxvYzFkKCZhcnIsIE4sICZtZW0pOwogIGZvcihpPSgwKTtpPChOKTtpKyspewogICAgYXJyW2ldLmZpcnN0ID0gYVtpXTsKICAgIGFycltpXS5zZWNvbmQuZmlyc3QgPSBiW2ldOwogICAgYXJyW2ldLnNlY29uZC5zZWNvbmQgPSBjW2ldOwogIH0KICBzb3J0KGFyciwgYXJyK04pOwogIGZvcihpPSgwKTtpPChOKTtpKyspewogICAgYVtpXSA9IGFycltpXS5maXJzdDsKICAgIGJbaV0gPSBhcnJbaV0uc2Vjb25kLmZpcnN0OwogICAgY1tpXSA9IGFycltpXS5zZWNvbmQuc2Vjb25kOwogIH0KfQp0ZW1wbGF0ZTxjbGFzcyBUMSwgY2xhc3MgVDIsIGNsYXNzIFQzLCBjbGFzcyBUND4gdm9pZCBzb3J0QShpbnQgTiwgVDEgYVtdLCBUMiBiW10sIFQzIGNbXSwgVDQgZFtdLCB2b2lkICptZW0gPSB3bWVtKXsKICBpbnQgaTsKICBwYWlyPHBhaXI8VDEsIFQyPiwgcGFpcjxUMywgVDQ+ID4qYXJyOwogIHdhbGxvYzFkKCZhcnIsIE4sICZtZW0pOwogIGZvcihpPSgwKTtpPChOKTtpKyspewogICAgYXJyW2ldLmZpcnN0LmZpcnN0ID0gYVtpXTsKICAgIGFycltpXS5maXJzdC5zZWNvbmQgPSBiW2ldOwogICAgYXJyW2ldLnNlY29uZC5maXJzdCA9IGNbaV07CiAgICBhcnJbaV0uc2Vjb25kLnNlY29uZCA9IGRbaV07CiAgfQogIHNvcnQoYXJyLCBhcnIrTik7CiAgZm9yKGk9KDApO2k8KE4pO2krKyl7CiAgICBhW2ldID0gYXJyW2ldLmZpcnN0LmZpcnN0OwogICAgYltpXSA9IGFycltpXS5maXJzdC5zZWNvbmQ7CiAgICBjW2ldID0gYXJyW2ldLnNlY29uZC5maXJzdDsKICAgIGRbaV0gPSBhcnJbaV0uc2Vjb25kLnNlY29uZDsKICB9Cn0KdGVtcGxhdGU8Y2xhc3MgVD4gdm9pZCBVbmlxdWUoaW50ICZOLCBUIEFbXSwgaW50IHNvcnRlZD0wLCB2b2lkICptd20gPSB3bWVtKXsKICBpbnQgaTsKICBpbnQgazsKICBpZighc29ydGVkKXsKICAgIHNvcnRBKE4sIEEpOwogIH0KICBrID0gMDsKICBmb3IoaT0oMCk7aTwoTik7aSsrKXsKICAgIGlmKGs9PTAgfHwgQVtrLTFdIT1BW2ldKXsKICAgICAgQVtrKytdID0gQVtpXTsKICAgIH0KICB9CiAgTiA9IGs7Cn0KdGVtcGxhdGU8Y2xhc3MgVCwgY2xhc3MgUz4gdm9pZCBVbmlxdWUoaW50ICZOLCBUIEFbXSwgUyBCW10sIGludCBzb3J0ZWQ9MCwgdm9pZCAqbWVtID0gd21lbSl7CiAgaW50IGk7CiAgaW50IGsgPSAwOwogIGlmKCFzb3J0ZWQpewogICAgc29ydEEoTiwgQSwgQiwgbWVtKTsKICB9CiAgZm9yKGk9KDApO2k8KE4pO2krKyl7CiAgICBpZighayB8fCBBW2stMV0hPUFbaV0pewogICAgICBBW2tdID0gQVtpXTsKICAgICAgQltrXSA9IEJbaV07CiAgICAgIGsrKzsKICAgIH0KICAgIGVsc2V7CiAgICAgIEJbay0xXSArPSBCW2ldOwogICAgfQogIH0KICBOPWs7Cn0KI2RlZmluZSBtYWluIGR1bW15X21haW4KaW50IG1haW4oKXsKICB3bWVtID0gbWVtYXJyOwogIHJldHVybiAwOwp9CiN1bmRlZiBtYWluCmludCBOOwppbnQgQVsxMDAwMDAwXTsKaW50IEJbMTAwMDAwMF07CmxvbmcgbG9uZyBva1sxMDAwMDAwXTsKbG9uZyBsb25nIHZhbFsxMDAwMDAwXTsKbG9uZyBsb25nIHhbMTAwMDAwMF07CmxvbmcgbG9uZyB5WzEwMDAwMDBdOwpjbGFzcyBTb2x1dGlvbnsKICBwdWJsaWM6CiAgaW50IG1pbkdyb3Vwc0ZvclZhbGlkQXNzaWdubWVudCh2ZWN0b3I8aW50PiAmbnVtcyl7CiAgICBkdW1teV9tYWluKCk7CiAgICBpbnQgaTsKICAgIGludCBqOwogICAgaW50IGs7CiAgICBpbnQgTSA9IG51bXMuc2l6ZSgpOwogICAgbG9uZyBsb25nIHJlcyA9IDQ2MTE2ODYwMTYyNzk5MDQyNTZMTDsKICAgIE4gPSBudW1zLnNpemUoKTsKICAgIGZvcihpPSgwKTtpPChOKTtpKyspewogICAgICBBW2ldID0gbnVtc1tpXTsKICAgICAgQltpXSA9IDE7CiAgICB9CiAgICBVbmlxdWUoTiwgQSwgQik7CiAgICBmb3IoaT0oMCk7aTwoTSsxKTtpKyspewogICAgICBva1tpXSA9IHZhbFtpXSA9IDA7CiAgICB9CiAgICBmb3IoaT0oMCk7aTwoTik7aSsrKXsKICAgICAgZm9yKGo9KDApO2o8KEJbaV0rMSk7aisrKXsKICAgICAgICB4W2pdID0gMDsKICAgICAgICB5W2pdID0gMTA3MzcwOTA1NjsKICAgICAgfQogICAgICBmb3Ioaj0oMSk7ajwoQltpXSsxKTtqKyspewogICAgICAgIGsgPSBCW2ldIC8gajsKICAgICAgICB4W2tdID0gMTsKICAgICAgICBjaG1pbih5W2tdLCBqKTsKICAgICAgICBpZihCW2ldJWo9PTApewogICAgICAgICAgeFtrLTFdID0gMTsKICAgICAgICAgIGNobWluKHlbay0xXSwgaik7CiAgICAgICAgfQogICAgICB9CiAgICAgIGZvcihqPSgwKTtqPChCW2ldKzEpO2orKyl7CiAgICAgICAgb2tbal0gKz0geFtqXTsKICAgICAgICB2YWxbal0gKz0geVtqXTsKICAgICAgfQogICAgfQogICAgZm9yKGk9KDEpO2k8KE0rMSk7aSsrKXsKICAgICAgaWYob2tbaV09PU4pewogICAgICAgIGNobWluKHJlcywgdmFsW2ldKTsKICAgICAgfQogICAgfQogICAgcmV0dXJuIHJlczsKICB9Cn0KOwovLyBjTGF5IHZlcnNpb24gMjAyMzEwMzEtMQoKLy8gLS0tIG9yaWdpbmFsIGNvZGUgLS0tCi8vICNkZWZpbmUgbWFpbiBkdW1teV9tYWluCi8vIHt9Ci8vICN1bmRlZiBtYWluCi8vIAovLyBpbnQgTiwgQVsxZDZdLCBCW107Ci8vIGxsIG9rW10sIHZhbFtdLCB4W10sIHlbXTsKLy8gCi8vIGNsYXNzIFNvbHV0aW9uIHsKLy8gcHVibGljOgovLyAgIGludCBtaW5Hcm91cHNGb3JWYWxpZEFzc2lnbm1lbnQoVkkgJm51bXMpIHsKLy8gICAgIGR1bW15X21haW4oKTsKLy8gICAgIGludCBpLCBqLCBrLCBNID0gbnVtcy5zaXplKCk7Ci8vICAgICBsbCByZXMgPSBsbF9pbmY7Ci8vICAgICBOID0gbnVtcy5zaXplKCk7Ci8vICAgICByZXAoaSxOKSBBW2ldID0gbnVtc1tpXSwgQltpXSA9IDE7Ci8vICAgICBVbmlxdWUoTiwgQSwgQik7Ci8vIAovLyAgICAgcmVwKGksTSsxKSBva1tpXSA9IHZhbFtpXSA9IDA7Ci8vICAgICByZXAoaSxOKXsKLy8gICAgICAgcmVwKGosQltpXSsxKSB4W2pdID0gMCwgeVtqXSA9IGludF9pbmY7Ci8vICAgICAgIHJlcChqLDEsQltpXSsxKXsKLy8gICAgICAgICBrID0gQltpXSAvIGo7Ci8vICAgICAgICAgeFtrXSA9IDE7Ci8vICAgICAgICAgeVtrXSA8Pz0gajsKLy8gICAgICAgICBpZihCW2ldJWo9PTApIHhbay0xXSA9IDEsIHlbay0xXSA8Pz0gajsKLy8gICAgICAgfQovLyAgICAgICByZXAoaixCW2ldKzEpIG9rW2pdICs9IHhbal0sIHZhbFtqXSArPSB5W2pdOwovLyAgICAgfQovLyAKLy8gICAgIHJlcChpLDEsTSsxKSBpZihva1tpXT09TikgcmVzIDw/PSB2YWxbaV07Ci8vICAgICByZXR1cm4gcmVzOwovLyAgIH0KLy8gfTsK