From 2ef6e7ee18922c4e653dd8a0512c424453aba9df Mon Sep 17 00:00:00 2001 From: Tom Lane Date: Tue, 20 Mar 2001 03:08:12 +0000 Subject: [PATCH] Repair intarray's problems with TOASTed input, avoid scribbling on source data, improve split algorithm for intbig_ops. Oleg Bartunov with some kibitzing from Tom Lane. --- contrib/intarray/README.intarray | 6 + contrib/intarray/_int.c | 384 ++--- contrib/intarray/data/test__int.data | 2000 ++++++++++++++++++++++++++ contrib/intarray/expected/_int.out | 6 +- 4 files changed, 2210 insertions(+), 186 deletions(-) diff --git a/contrib/intarray/README.intarray b/contrib/intarray/README.intarray index dc7cc9a88d..26cb082e3a 100644 --- a/contrib/intarray/README.intarray +++ b/contrib/intarray/README.intarray @@ -10,6 +10,12 @@ All work was done by Teodor Sigaev (teodor@stack.net) and Oleg Bartunov (oleg@sai.msu.su). See http://www.sai.msu.su/~megera/postgres/gist for additional information. +CHANGES: + +March 19, 2001 + 1. Added support for toastable keys + 2. Improved split algorithm for intbig (selection speedup is about 30%) + INSTALLATION: gmake diff --git a/contrib/intarray/_int.c b/contrib/intarray/_int.c index 3d615ef2c4..352f5ce48f 100644 --- a/contrib/intarray/_int.c +++ b/contrib/intarray/_int.c @@ -4,6 +4,11 @@ format for these routines is dictated by Postgres architecture. ******************************************************************************/ +/* +#define GIST_DEBUG +#define GIST_QUERY_DEBUG +*/ + #include "postgres.h" #include @@ -17,32 +22,46 @@ #include "utils/builtins.h" #include "storage/bufpage.h" +/* number ranges for compression */ #define MAXNUMRANGE 100 #define max(a,b) ((a) > (b) ? (a) : (b)) #define min(a,b) ((a) <= (b) ? (a) : (b)) #define abs(a) ((a) < (0) ? -(a) : (a)) +/* dimension of array */ +#define NDIM 1 + +/* useful macros for accessing int4 arrays */ #define ARRPTR(x) ( (int4 *) ARR_DATA_PTR(x) ) #ifdef PGSQL71 -#define ARRSIZE(x) ArrayGetNItems( ARR_NDIM(x), ARR_DIMS(x)) +#define ARRNELEMS(x) ArrayGetNItems( ARR_NDIM(x), ARR_DIMS(x)) #else -#define ARRSIZE(x) getNitems( ARR_NDIM(x), ARR_DIMS(x)) +#define ARRNELEMS(x) getNitems( ARR_NDIM(x), ARR_DIMS(x)) #endif -#define NDIM 1 +#define ARRISNULL(x) ( (x) ? ( ( ARR_NDIM(x) == NDIM ) ? ( ( ARRNELEMS( x ) ) ? 0 : 1 ) : 1 ) : 1 ) + +#define SORT(x) \ + do { \ + if ( ARRNELEMS( x ) > 1 ) \ + isort( (void*)ARRPTR( x ), ARRNELEMS( x ) ); \ + } while(0) -#define ARRISNULL(x) ( (x) ? ( ( ARR_NDIM(x) == NDIM ) ? ( ( ARRSIZE( x ) ) ? 0 : 1 ) : 1 ) : 1 ) -#define SORT(x) if ( ARRSIZE( x ) > 1 ) isort( (void*)ARRPTR( x ), ARRSIZE( x ) ); #define PREPAREARR(x) \ - if ( ARRSIZE( x ) > 1 ) {\ - if ( isort( (void*)ARRPTR( x ), ARRSIZE( x ) ) )\ - x = _int_unique( x );\ - } + do { \ + if ( ARRNELEMS( x ) > 1 ) \ + if ( isort( (void*)ARRPTR( x ), ARRNELEMS( x ) ) ) \ + x = _int_unique( x ); \ + } while(0) + +/* "wish" function */ +#define WISH_F(a,b,c) (double)( -(double)(((a)-(b))*((a)-(b))*((a)-(b)))*(c) ) + /* bigint defines */ #define BITBYTE 8 -#define SIGLENINT 128 +#define SIGLENINT 64 /* >122 => key will toast, so very slow!!! */ #define SIGLEN ( sizeof(int)*SIGLENINT ) #define SIGLENBIT (SIGLEN*BITBYTE) @@ -50,10 +69,6 @@ typedef char BITVEC[SIGLEN]; typedef char* BITVECP; #define SIGPTR(x) ( (BITVECP) ARR_DATA_PTR(x) ) -#define NULLIFY(a) MemSet( a, 0, sizeof( BITVEC ) ) -#define NEWSIG(a) \ - a=(BITVECP) malloc( sizeof( BITVEC ) );\ - NULLIFY(a); #define LOOPBYTE(a) \ for(i=0;i> ( (i) % BITBYTE )) & 0x01 ) -#define union_sig(a,b,r) LOOPBYTE(r[i] = a[i] | b[i]) -#define inter_sig(a,b,r) LOOPBYTE(r[i] = a[i] & b[i]) -/* -#define GIST_DEBUG -#define GIST_QUERY_DEBUG -*/ #ifdef GIST_DEBUG static void printarr ( ArrayType * a, int num ) { char bbb[16384]; @@ -87,7 +96,7 @@ static void printarr ( ArrayType * a, int num ) { d = ARRPTR( a ); *bbb = '\0'; cur = bbb; - for(l=0; lpred ) ) { +#ifdef PGSQL71 + if ( entry->pred ) + r = (ArrayType *)PG_DETOAST_DATUM_COPY( entry->pred ); + else + r = NULL; +#else + r = copy_intArrayType( (ArrayType *) entry->pred ); +#endif + + if ( ARRISNULL( r ) ) { #ifdef GIST_DEBUG elog(NOTICE,"COMP IN: NULL"); #endif - gistentryinit(*retval, (char *)NULL, entry->rel, entry->page, entry->offset, - 0, FALSE); + if ( r ) if ( (char*)r != (char*)entry->pred ) pfree(r); + + gistentryinit(*retval, (char *)NULL, entry->rel, entry->page, entry->offset, + 0, FALSE); return( retval ); } - - r = copy_intArrayType( (ArrayType *) entry->pred ); + if ( entry->leafkey ) PREPAREARR( r ); - len = ARRSIZE( r ); + len = ARRNELEMS( r ); #ifdef GIST_DEBUG elog(NOTICE, "COMP IN: %d leaf; %d rel; %d page; %d offset; %d bytes; %d elems", entry->leafkey, (int)entry->rel, (int)entry->page, (int)entry->offset, (int)entry->bytes, len); @@ -297,10 +317,21 @@ g_int_decompress(GISTENTRY *entry) int *din; int i,j; - if ( entry->bytes < ARR_OVERHEAD( NDIM ) || ARRISNULL( (ArrayType *) entry->pred ) ) { +#ifdef PGSQL71 + if ( entry->pred ) + in = (ArrayType *)PG_DETOAST_DATUM( entry->pred ); + else + in = NULL; +#else + in = (ArrayType *) entry->pred; +#endif + + if ( entry->bytes < ARR_OVERHEAD( NDIM ) || ARRISNULL( in ) ) { retval = palloc(sizeof(GISTENTRY)); - if ( ! retval ) - elog(ERROR,"Can't allocate memory for decompression"); + +#ifdef PGSQL71 + if ( in ) if ( (char*)in != (char*)entry->pred ) pfree(in); +#endif gistentryinit(*retval, (char *)NULL, entry->rel, entry->page, entry->offset, 0, FALSE); #ifdef GIST_DEBUG elog(NOTICE,"DECOMP IN: NULL"); @@ -309,8 +340,7 @@ g_int_decompress(GISTENTRY *entry) } - in = (ArrayType *) entry->pred; - lenin = ARRSIZE(in); + lenin = ARRNELEMS(in); din = ARRPTR(in); if ( lenin < 2*MAXNUMRANGE ) { /*not comressed value*/ @@ -333,9 +363,11 @@ g_int_decompress(GISTENTRY *entry) if ( (!i) || *(dr-1) != j ) *dr++ = j; +#ifdef PGSQL71 + if ( (char*)in != (char*)entry->pred ) pfree(in); +#endif retval = palloc(sizeof(GISTENTRY)); - if ( ! retval ) - elog(ERROR,"Can't allocate memory for decompression"); + gistentryinit(*retval, (char *)r, entry->rel, entry->page, entry->offset, VARSIZE( r ), FALSE); return(retval); @@ -355,11 +387,11 @@ GIST_SPLITVEC * g_int_picksplit(bytea *entryvec, GIST_SPLITVEC *v) { - return _int_common_picksplit( entryvec, v, inner_int_union, inner_int_inter, - rt__int_size); + rt__int_size, + 1e-8); } /* @@ -387,6 +419,7 @@ bool _int_contains ( ArrayType *a, ArrayType *b ) { bool res; ArrayType *an, *bn; + if ( ARRISNULL( a ) || ARRISNULL( b ) ) return FALSE; an = copy_intArrayType( a ); @@ -408,8 +441,8 @@ inner_int_contains ( ArrayType *a, ArrayType *b ) { if ( ARRISNULL( a ) || ARRISNULL( b ) ) return FALSE; - na = ARRSIZE( a ); - nb = ARRSIZE( b ); + na = ARRNELEMS( a ); + nb = ARRNELEMS( b ); da = ARRPTR( a ); db = ARRPTR( b ); @@ -444,39 +477,62 @@ _int_same ( ArrayType *a, ArrayType *b ) { int na , nb ; int n; int *da, *db; + bool result; + ArrayType *an, *bn; bool anull = ARRISNULL( a ); bool bnull = ARRISNULL( b ); if ( anull || bnull ) return ( anull && bnull ) ? TRUE : FALSE; - - SORT( a ); - SORT( b ); - na = ARRSIZE( a ); - nb = ARRSIZE( b ); - da = ARRPTR( a ); - db = ARRPTR( b ); - if ( na != nb ) return FALSE; - - n = 0; + an = copy_intArrayType( a ); + bn = copy_intArrayType( b ); + + SORT( an ); + SORT( bn ); + na = ARRNELEMS( an ); + nb = ARRNELEMS( bn ); + da = ARRPTR( an ); + db = ARRPTR( bn ); + + result = FALSE; + + if ( na == nb ) + { + result = TRUE; for(n=0; n 1 ) + if ( ARRNELEMS(r) > 1 ) r = _int_unique( r ); return r; @@ -564,12 +631,22 @@ inner_int_union ( ArrayType *a, ArrayType *b ) { ArrayType * _int_inter ( ArrayType *a, ArrayType *b ) { - if ( ARRISNULL( a ) || ARRISNULL( b ) ) return FALSE; + ArrayType *result; + ArrayType *an, *bn; - SORT(a); - SORT(b); + if ( ARRISNULL( a ) || ARRISNULL( b ) ) return new_intArrayType(0); + + an = copy_intArrayType( a ); + bn = copy_intArrayType( b ); + + SORT(an); + SORT(bn); - return inner_int_inter( a, b ); + result = inner_int_inter( an, bn ); + + pfree( an ); pfree( bn ); + + return result; } ArrayType * @@ -583,10 +660,10 @@ inner_int_inter ( ArrayType *a, ArrayType *b ) { elog(NOTICE, "inner_inter %d %d", ARRISNULL( a ), ARRISNULL( b ) ); #endif - if ( ARRISNULL( a ) || ARRISNULL( b ) ) return NULL; + if ( ARRISNULL( a ) || ARRISNULL( b ) ) return new_intArrayType(0); - na = ARRSIZE( a ); - nb = ARRSIZE( b ); + na = ARRNELEMS( a ); + nb = ARRNELEMS( b ); da = ARRPTR( a ); db = ARRPTR( b ); r = new_intArrayType( min(na, nb) ); @@ -605,7 +682,7 @@ inner_int_inter ( ArrayType *a, ArrayType *b ) { if ( (dr - ARRPTR(r)) == 0 ) { pfree( r ); - return NULL; + return new_intArrayType(0); } else return resize_intArrayType(r, dr - ARRPTR(r) ); } @@ -616,7 +693,7 @@ rt__int_size(ArrayType *a, float *size) if ( ARRISNULL( a ) ) *size = 0.0; else - *size = (float)ARRSIZE( a ); + *size = (float)ARRNELEMS( a ); return; } @@ -654,8 +731,7 @@ new_intArrayType( int num ) { int nbytes = ARR_OVERHEAD( NDIM ) + sizeof(int)*num; r = (ArrayType *) palloc( nbytes ); - if ( ! r ) - elog(ERROR, "Can't allocate memory for new array"); + MemSet(r, 0, nbytes); r->size = nbytes; r->ndim = NDIM; @@ -672,11 +748,9 @@ static ArrayType * resize_intArrayType( ArrayType * a, int num ) { int nbytes = ARR_OVERHEAD( NDIM ) + sizeof(int)*num; - if ( num == ARRSIZE(a) ) return a; + if ( num == ARRNELEMS(a) ) return a; a = (ArrayType *) repalloc( a, nbytes ); - if ( ! a ) - elog(ERROR, "Can't reallocate memory for new array"); a->size = nbytes; *( (int*)ARR_DIMS(a) ) = num; @@ -686,8 +760,8 @@ resize_intArrayType( ArrayType * a, int num ) { static ArrayType * copy_intArrayType( ArrayType * a ) { ArrayType * r; - if ( ! a ) return NULL; - r = new_intArrayType( ARRSIZE(a) ); + if ( ARRISNULL(a) ) return NULL; + r = new_intArrayType( ARRNELEMS(a) ); memmove(r,a,VARSIZE(a)); return r; } @@ -708,7 +782,7 @@ internal_size (int *a, int len ) { static ArrayType * _int_unique( ArrayType * r ) { int *tmp, *dr, *data; - int num = ARRSIZE(r); + int num = ARRNELEMS(r); data = tmp = dr = ARRPTR( r ); while( tmp - data < num ) if ( *tmp != *dr ) @@ -721,15 +795,14 @@ _int_unique( ArrayType * r ) { /********************************************************************* ** intbig functions *********************************************************************/ - static void gensign(BITVEC sign, int * a, int len) { int i; - NULLIFY(sign); - for(i=0; ileafkey ) return entry; retval = palloc(sizeof(GISTENTRY)); - if ( ! retval ) - elog(ERROR,"Can't allocate memory for compression"); if ( ARRISNULL( in ) ) { #ifdef PGSQL71 @@ -876,8 +940,8 @@ g_intbig_compress(GISTENTRY *entry) { r = new_intArrayType( SIGLENINT ); gensign( SIGPTR( r ), ARRPTR ( in ), - ARRSIZE( in ) ); - + ARRNELEMS( in ) ); + gistentryinit(*retval, (char *)r, entry->rel, entry->page, entry->offset, VARSIZE( r ), FALSE); #ifdef PGSQL71 @@ -889,72 +953,28 @@ g_intbig_compress(GISTENTRY *entry) { GISTENTRY * g_intbig_decompress(GISTENTRY *entry) { +#ifdef PGSQL71 + ArrayType *key; + key = (ArrayType *)PG_DETOAST_DATUM( entry->pred ); + if ( (char*)key != (char*)entry->pred ) { + GISTENTRY *retval; + retval = palloc(sizeof(GISTENTRY)); + + gistentryinit(*retval, (char *)key, entry->rel, entry->page, entry->offset, VARSIZE( key ), FALSE); + return retval; + } +#endif return entry; } GIST_SPLITVEC * g_intbig_picksplit(bytea *entryvec, GIST_SPLITVEC *v) { + return _int_common_picksplit( entryvec, v, + _intbig_union, + _intbig_inter, + rt__intbig_size, + 1.0); - OffsetNumber k; - ArrayType *datum_l, *datum_r, *datum_alpha; - ArrayType *unionarr; - float size_l, size_r; - int nbytes; - OffsetNumber *left, *right; - OffsetNumber maxoff; - -#ifdef GIST_DEBUG - elog(NOTICE, "--------picksplit %d",(VARSIZE(entryvec) - VARHDRSZ)/sizeof(GISTENTRY)); -#endif - - maxoff = ((VARSIZE(entryvec) - VARHDRSZ)/sizeof(GISTENTRY)) - 2; - nbytes = (maxoff + 2) * sizeof(OffsetNumber); - v->spl_left = (OffsetNumber *) palloc(nbytes); - v->spl_right = (OffsetNumber *) palloc(nbytes); - left = v->spl_left; - v->spl_nleft = 0; - right = v->spl_right; - v->spl_nright = 0; - - maxoff = OffsetNumberNext(maxoff); - datum_l = datum_r = NULL; - - for (k = FirstOffsetNumber; k <= maxoff; k = OffsetNumberNext(k)) { - datum_alpha = (ArrayType *)(((GISTENTRY *)(VARDATA(entryvec)))[k].pred); - - if ( k != FirstOffsetNumber ) { - unionarr = (ArrayType *)_intbig_union(datum_l, datum_alpha); - if ( datum_l ) pfree(datum_l); - datum_l = unionarr; - rt__intbig_size((ArrayType *)unionarr, &size_l); - *left++ = k; - v->spl_nleft++; - } else { - unionarr = (ArrayType *)_intbig_union(datum_r, datum_alpha); - if ( datum_r ) pfree(datum_r); - datum_r = unionarr; - rt__intbig_size((ArrayType *)unionarr, &size_r); - *right++ = k; - v->spl_nright++; - } - } - - if ( *(left-1) > *(right-1) ) { - *right = FirstOffsetNumber; - *(left-1) = InvalidOffsetNumber; - } else { - *left = FirstOffsetNumber; - *(right-1) = InvalidOffsetNumber; - } - - - v->spl_ldatum = (char *)datum_l; - v->spl_rdatum = (char *)datum_r; - -#ifdef GIST_DEBUG - elog(NOTICE, "--------ENDpicksplit %d %d",v->spl_nleft, v->spl_nright); -#endif - return v; } ArrayType * @@ -965,7 +985,6 @@ g_intbig_union(bytea *entryvec, int *sizep) { float * g_intbig_penalty(GISTENTRY *origentry, GISTENTRY *newentry, float *result){ _int_common_penalty( origentry, newentry, result, _intbig_union, rt__intbig_size); - *result= SIGLENBIT - *result; return result; } @@ -974,13 +993,13 @@ g_intbig_consistent(GISTENTRY *entry, ArrayType *query, StrategyNumber strategy) bool retval; ArrayType * q; + /* XXX what about toasted input? */ if ( ARRISNULL( query ) ) return FALSE; q = new_intArrayType( SIGLENINT ); - gensign( SIGPTR( q ), ARRPTR( query ), - ARRSIZE( query ) ); + ARRNELEMS( query ) ); switch(strategy) { case RTOverlapStrategyNumber: @@ -1042,9 +1061,10 @@ _int_common_union(bytea *entryvec, int *sizep, formarray unionf) { } -/* -** The GiST Penalty method for _intments -*/ +/***************************************** + * The GiST Penalty method for _intments * + *****************************************/ + float * _int_common_penalty(GISTENTRY *origentry, GISTENTRY *newentry, float *result, formarray unionf, @@ -1063,7 +1083,7 @@ _int_common_penalty(GISTENTRY *origentry, GISTENTRY *newentry, float *result, pfree((char *)ud); #ifdef GIST_DEBUG - elog(NOTICE, "--penalty\t%g\t%g\t%g", *result, tmp1, tmp2); + elog(NOTICE, "--penalty\t%g", *result); #endif return(result); @@ -1078,7 +1098,8 @@ _int_common_picksplit(bytea *entryvec, GIST_SPLITVEC *v, formarray unionf, formarray interf, - formfloat sizef) + formfloat sizef, + float coef) { OffsetNumber i, j; ArrayType *datum_alpha, *datum_beta; @@ -1105,7 +1126,7 @@ _int_common_picksplit(bytea *entryvec, firsttime = true; waste = 0.0; - + for (i = FirstOffsetNumber; i < maxoff; i = OffsetNumberNext(i)) { datum_alpha = (ArrayType *)(((GISTENTRY *)(VARDATA(entryvec)))[i].pred); for (j = OffsetNumberNext(i); j <= maxoff; j = OffsetNumberNext(j)) { @@ -1137,7 +1158,7 @@ _int_common_picksplit(bytea *entryvec, } } } - + left = v->spl_left; v->spl_nleft = 0; right = v->spl_right; @@ -1163,7 +1184,6 @@ _int_common_picksplit(bytea *entryvec, */ maxoff = OffsetNumberNext(maxoff); - for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i)) { @@ -1192,7 +1212,7 @@ _int_common_picksplit(bytea *entryvec, (*sizef)((ArrayType *)union_dr, &size_beta); /* pick which page to add it to */ - if (size_alpha - size_l < size_beta - size_r) { + if (size_alpha - size_l < size_beta - size_r + WISH_F(v->spl_nleft, v->spl_nright, coef)) { if ( datum_l ) pfree(datum_l); if ( union_dr ) pfree(union_dr); datum_l = union_dl; @@ -1208,7 +1228,6 @@ _int_common_picksplit(bytea *entryvec, v->spl_nright++; } } - /**left = *right = FirstOffsetNumber;*/ /* sentinel value, see dosplit() */ if ( *(left-1) > *(right-1) ) { *right = FirstOffsetNumber; @@ -1218,7 +1237,6 @@ _int_common_picksplit(bytea *entryvec, *(right-1) = InvalidOffsetNumber; } - v->spl_ldatum = (char *)datum_l; v->spl_rdatum = (char *)datum_r; diff --git a/contrib/intarray/data/test__int.data b/contrib/intarray/data/test__int.data index 82345f0cc6..9750bf0363 100644 --- a/contrib/intarray/data/test__int.data +++ b/contrib/intarray/data/test__int.data @@ -4998,3 +4998,2003 @@ {86,31} {69,90,95,66} {6,10} +{68,72,112} +{9,165} +{91,132,164} +{57,82,144,167,184} +{3,6,101,118} +{111,158} +{22,29,30,174} +{41,66} +{39,76,189} +{7,20,21,196} +{52,126,169,171,184} +{21,77,91,176,196} +{16,97,121} +{83,135,137} +{8,140,160,164,165,195} +{38,65,185} +{112,152} +{111,129,134,148} +{47,80,114,135,147,165} +{24,98,119,123} +{43,48,60,147,154} +{19,54,138,171,186} +{156,175} +{20,51,123,193,193} +{37,41,136,173,192} +{14,22,111,125} +{44,125,160,184} +{19,75,99,103,107,164} +{24,113,145} +{27,157} +{12,107,133,134} +{72,94,102,158,194} +{104,157} +{122,171} +{28,47,89,104,112} +{25,35,82,105,155} +{106,107,139,181} +{50,110,132,136} +{90,110,166} +{1,1,55,60,85,108} +{8,22,31,106,172,196} +{24,69,109,121,154} +{0,26,44,59,132,175} +{103,125,172,188,190} +{11,23,78,109,131} +{81,146,169,181,196} +{2,84,113,189} +{8,46,126,131} +{13,73,73,125,127} +{67,117,139,184} +{29,65,77,120,182} +{0,87,100,102,135} +{111,146,156} +{13,87,123,137,182,197} +{60,61,164} +{7,20,186} +{0,24,53,135,147} +{94,136} +{47,168} +{70,80} +{43,148} +{3,81,104,191} +{104,171,189} +{9,14,117,160,180} +{67,158} +{50,57,66,78,170,197} +{31,60,73,101,193,197} +{37,89,92,96,127} +{29,179} +{17,47,137,155,157,187} +{33,77,154} +{48,63,85,150,184} +{32,53,61,95,172} +{20,35,47,171,179,196} +{2,17,40,169,184} +{116,127,131,142} +{16,26,27,87,164,198} +{58,129} +{67,98,108,132,157,197} +{145,157} +{13,49,56} +{59,103,180,196} +{35,65,104,106,120,126} +{18,96,115,133} +{27,61} +{61,194,197} +{11,27,36,94} +{15,36,101,128,197} +{51,62,115,149} +{83,198} +{30,120,127,145,184} +{50,149} +{13,35,87,117,135,158} +{57,60,74,113,128,178} +{11,90,123,163,170} +{39,121,148,171,198,199} +{30,77,78,137,140,162} +{52,69,120,141} +{9,100,137} +{56,161} +{44,57,75,110,154} +{98,123,155,167} +{10,60,85,105,164,168} +{13,92,179,186} +{13,171,173,176,178} +{33,53,88,123,144,172} +{21,57,70,131,151} +{13,51,63,169,169} +{36,104,119,166} +{54,59,84,166,172} +{7,87,100,102,142,187} +{2,5,6,43,174} +{4,26,29,59,77} +{10,82,98,103,104} +{104,147} +{47,55,99} +{102,154,165} +{0,96,107,139,157,159} +{66,167,174} +{92,97,117} +{21,75,180,185} +{54,64,139,180} +{23,141,189} +{32,38,147} +{82,87} +{6,34,34,161,183} +{25,64,69,97,122} +{80,152,170,189} +{44,78,143,162} +{52,53,64,69,112,158} +{77,80,123,150,175} +{110,121,125,125,128,198} +{0,8,57,104,127,188} +{17,46,48,93,129,150} +{135,193} +{89,111,135,166,184} +{132,181} +{47,54,101,108,125} +{18,55,103,142} +{11,125} +{18,49,58,68,122,153} +{37,47,137,179,185} +{57,78,167,187,192} +{28,32,38,67,77,184} +{67,83} +{43,104,191} +{22,40,118,194} +{24,53,66,195} +{27,87,89,101,130,191} +{71,86,157,167,183} +{31,87,102} +{48,53,70,101,149,174} +{21,33,59,129,195} +{144,160} +{4,8,174,194} +{69,103,127,127,160} +{6,29,62,77,132} +{61,69,108,144,174} +{51,55,109,128,153} +{10,30} +{2,5,6,70,146,183} +{0,1,75,97,166,180} +{53,78,104} +{31,45,68,108,161} +{3,40,78,103,109,130} +{33,44,159} +{28,82,93,136,148,157} +{31,32,76,143,157} +{2,55,106} +{21,66,80,129,129,152} +{1,34,59,128,154,195} +{10,154,172,177} +{2,7,31,47,82,125} +{60,131,149,156} +{20,141} +{23,38,43,100} +{51,70} +{3,41,164} +{126,160,165,169} +{61,71,143} +{65,70,81,100,146} +{40,48,57,75,85,85} +{116,153} +{31,42,49,103,183} +{28,44,62,85,133,177} +{50,68,164,170} +{4,26,60,87,119,141} +{5,102,160} +{20,129,177} +{98,120,135,157,164,168} +{66,150} +{101,101} +{164,187} +{43,65,96,166,189} +{18,36,58,109,118} +{25,32,135,161,170} +{55,104,183} +{69,139,144,181,182} +{84,131,155} +{6,18,63,156,159} +{7,66,67,88} +{8,46,52,95,178} +{58,58,83,119,119,163} +{27,143} +{78,80,122,149,164,176} +{6,83,107,183,198} +{86,199} +{22,74} +{28,62,64,114} +{15,56} +{41,97,139,152,161,161} +{48,192} +{16,62,99,138,155} +{32,84,145} +{108,137} +{93,112,120,155} +{73,117} +{20,26,197} +{4,141} +{110,132} +{95,133,142,152,183,193} +{85,141} +{53,76,86,131} +{5,59,73,74,101,130} +{0,1,64,151,188} +{15,131,131,174} +{80,98,106,187} +{41,102,167,173} +{9,42,133} +{103,110,110,134,175,185} +{168,187} +{42,47,108,121,165,198} +{81,171} +{38,122,123,149} +{16,79} +{45,64,131,176,182,197} +{35,82,87,100,123,196} +{41,52} +{33,68} +{60,140} +{12,41,152} +{54,71} +{88,95,95,146,148,180} +{47,66,89,121,168,182} +{15,70,94,122,137,154} +{42,48,129,162} +{70,151} +{11,55,89,118} +{36,74,121,130,152} +{46,48,52,120,179} +{70,81} +{96,146,183} +{76,78,108,153} +{71,168} +{66,106,108,167} +{22,44,49,85,87,195} +{17,52,143,175} +{86,103} +{16,46,176} +{95,111,162,173,198} +{44,191} +{7,48,107,115,116} +{12,120,141,179,184} +{83,188} +{83,85,86,139,154} +{50,74,89,154,179} +{79,87,120,128,183} +{13,121} +{16,52,62,86,168,199} +{7,16,29,35,157,181} +{23,48,65,119,180} +{10,173} +{7,98,128,143,145,162} +{23,27,88,91,127} +{35,53,56,56,118} +{7,161} +{0,42,67,174} +{44,161} +{75,80,110,170} +{17,93,117,140,168,196} +{18,100,150,184} +{108,132} +{54,90,97,103,149} +{9,12,30,43,82,95} +{131,163} +{67,99,168} +{91,150,172} +{47,164,195} +{72,90,98} +{24,78,130,172} +{1,27,32,64,66,156} +{7,26,72,88,130,140} +{56,126,130} +{1,76,81,122,169,188} +{60,154} +{101,103,135,150} +{22,25,33} +{99,117} +{24,95,122,186} +{48,95,102,108,125,170} +{13,113,154} +{155,177} +{37,73,106} +{7,64,124,195} +{101,124,133,157,166,188} +{27,34,60,100} +{26,104,163} +{34,43,108,133,165} +{64,79,89,122,132} +{10,96,168} +{2,22,89,118,122,198} +{122,192} +{42,101,104,135,168,181} +{7,38,63,86,101,152} +{29,84,89,114,123,184} +{33,46,59,137,153,175} +{3,54,66,92} +{31,34,148,159,185} +{3,52,97,99} +{3,26} +{42,57,62,148,199} +{15,26,198} +{14,34,109,111,128,193} +{107,197} +{16,107} +{9,21,136,169} +{67,97,99,153,165,173} +{46,76,89,100,164} +{96,102,150,167,180} +{31,103,137,146,180} +{21,40,157,163,170,183} +{139,170} +{1,75,82,148,169,198} +{13,39,107} +{13,50,97,101,106} +{52,176} +{18,169} +{129,140,146,183,189} +{95,122,145} +{5,6,102,130,151} +{5,118,140,153} +{27,78,140,164,182} +{36,140,148} +{58,100,127} +{9,16} +{26,33,119} +{1,17,18,165} +{14,182} +{11,13,48,89,140,165} +{9,19,78,113} +{121,171} +{18,23,46,113,159,162} +{17,104} +{50,104,132,167,179} +{55,89,102,132,176} +{19,109} +{60,70,73,153,163} +{18,127,145} +{80,106,146,170} +{10,39,72,74,84,150} +{3,71} +{1,10,64} +{82,95,127,132,141,152} +{43,55,57,89,120,197} +{155,182} +{23,34,57,111,153} +{99,188} +{86,114,124} +{113,191} +{31,129,184} +{125,159,159} +{22,27,81,156} +{3,54,80,122,128,168} +{76,112} +{152,174} +{22,27,70,172} +{26,86} +{49,59,102,186} +{53,55,75,125} +{152,199} +{11,15,46,102,105,168} +{132,148,154} +{24,114,121,126,138,165} +{82,107} +{36,93,122,184,194} +{1,59,76,146} +{73,165} +{38,98,176} +{53,72,121,153} +{127,147} +{31,77,128,177} +{107,186,189} +{119,126,127,160} +{24,74,148,197} +{85,126,134,146} +{76,77,81,134} +{67,112,159,174,183} +{22,169,170} +{79,112,177,199} +{1,56} +{21,42,50,172} +{6,63,105,166,189} +{31,95,106,152,171,177} +{21,49,99,101,122,187} +{63,104,113,161,186} +{37,126,144,166,173} +{32,53,147} +{123,123,130} +{78,85,177} +{2,69,95,146,187} +{6,11,14,43,121} +{76,105,184} +{63,96,114,122,195} +{11,22,34,45,120,156} +{22,83,119,131,138,167} +{9,56,96,106,114} +{92,132,162} +{25,45,83,119,139,150} +{19,21,56,59,141} +{14,26,62,119,180,190} +{6,34,49,99,139,170} +{10,56,150,166,166} +{14,57,119,153,167,198} +{26,41,150,158,169} +{152,167} +{1,61,93,180} +{46,110,138,199} +{4,56,81,110,173} +{28,32,148,185} +{8,9,28,29,39,195} +{14,39,68,144} +{26,37,79,81,110} +{115,158,161} +{6,39,145,191} +{67,118,125,142,184,198} +{127,163} +{52,118} +{22,78,131,156} +{46,68,86,142,145,197} +{85,188} +{37,54,64,147,158} +{31,134,141,183,185} +{10,33,135,198} +{41,124,173,180} +{0,14,92,129,154,198} +{39,73,128,154,182,196} +{40,83,94,168} +{106,142} +{76,99} +{19,62,77,108,165,186} +{68,90,97,119,176} +{44,108,193} +{2,124} +{137,174,175,176,180} +{28,62,81,132,165,186} +{98,112,148,181} +{86,125} +{70,161} +{5,13,188} +{136,168} +{82,87} +{30,42,57} +{132,136,152} +{20,59,87,98,195} +{6,53,112,113,183,195} +{64,147,157} +{61,140,192} +{44,59,88,123,161} +{90,175} +{38,46,105,121,159} +{35,62,66,90,155} +{2,2,21,38} +{123,144} +{117,155} +{60,86} +{4,39,129,146,179} +{66,71,87,135,148,157} +{29,67,108,196} +{30,64,76,124,172} +{36,39,79,130,140,149} +{30,44,136,196} +{5,15,20,117,198} +{20,87,87,121} +{42,136,142,148} +{0,56} +{16,38,56,57} +{52,138} +{103,115} +{10,29,43,93,120,134} +{44,140,150,180} +{74,98,132,160} +{2,62,98,160} +{14,32,43,63,92} +{23,87,128,152,177,197} +{30,86,111,178,180} +{49,61,114,195,196} +{133,158,195} +{18,105,165,190} +{77,83,175} +{29,33,51,166,188} +{37,51,96,103,127} +{119,125,128,140} +{8,80,93,189} +{76,96,110,131,170} +{81,90} +{13,25,28,41,128,142} +{56,62,73,110} +{60,62,128,136,166,193} +{34,34,61,74} +{32,84,87,92,112,181} +{10,66,93,153} +{23,77,182} +{2,7,156} +{5,13,49,61,103,179} +{67,136,136,163,181,196} +{26,60,74,100,160} +{39,59,69,93,111} +{9,77,90} +{1,20,52,75,156,169} +{25,95,103,157,163,193} +{95,136} +{47,108,137,157,164} +{37,99,151,153,169,189} +{112,126,139,171,184,195} +{39,188} +{4,20,71,80,136,156} +{24,33,77,82} +{103,188} +{74,116} +{82,90,110,154,194,195} +{25,149,180} +{120,123,130,171} +{20,38,104,126,175,176} +{14,62,97,130,135,193} +{35,118} +{20,42,64,73,76,120} +{11,40,60,74,144,148} +{13,26,46,63,76} +{24,29,98,106} +{6,139,171,186} +{5,109,197} +{20,45,84,125} +{1,137,150,195} +{1,8,80,111} +{57,90,102,167} +{53,186} +{8,31,115,145,156,165} +{10,18,31,116,164} +{43,47} +{33,143,154} +{106,153,174,190} +{73,106,158} +{18,137,158,173} +{73,80,107,123,141,199} +{17,43,123,130,130,155} +{15,31,37,91,164,181} +{38,86} +{49,105,142,145,173,190} +{18,107,108,135,138} +{43,65,107,112,193} +{8,68,68,74} +{54,106,108,109,164} +{53,153} +{59,134,154,173,180} +{34,93} +{11,33,124} +{8,104} +{27,37,46,65,125,174} +{0,122,189} +{15,74,107,147,188} +{35,63,78} +{28,49,123,129,177,193} +{11,89,104} +{117,171,197} +{11,15,62,136,145,145} +{2,127,193} +{17,28,42,113,145} +{31,44,118,148} +{52,103,128,161,182} +{45,47,70,102,161,184} +{15,52,82,86} +{60,87,102,108,127,170} +{24,57,102,145,181} +{12,53} +{5,52,92,129,164} +{87,128} +{80,143,170} +{59,85,134,139} +{61,67,110,117,156,157} +{6,8,60,112,154,170} +{92,122,133} +{121,148,161} +{9,22,61,187} +{12,40,78,107,176} +{30,45,58,189,198} +{83,107,123,148} +{3,66,98,124,126,150} +{13,34} +{16,41,132} +{16,85} +{3,25} +{30,58,138,167} +{24,36,87,151,159,186} +{2,4,121,196} +{79,95,99,107} +{11,49,146,169} +{51,90} +{76,155} +{26,26,116,120,146,182} +{44,66,72,117,132,174} +{7,161,179,197} +{2,81,158} +{4,22,59,107,146,170} +{0,0,133,192} +{57,82} +{17,61} +{28,29,42,77,89,124} +{53,78,127,188} +{31,57,103,104,162} +{9,84,100} +{3,52,114,133,161,188} +{8,37,97,158,189} +{0,13,88} +{29,79,92,158,160,171} +{59,63,77,139,165} +{25,77,116,169} +{50,88,151,166} +{52,162,167} +{32,149,191,194,194} +{47,57,74,95,97} +{30,65,96,153,184} +{80,130,150,172} +{79,91,141,153,157} +{93,110,114,194} +{62,66,156,175} +{55,56,97,117} +{74,152,171,186} +{13,24,50,50,131} +{0,16,95,141,146,161} +{1,51,158} +{37,71,96,122} +{71,104,145} +{47,52,124,131,169} +{111,188} +{59,61,95,152,156,157} +{5,31,106,164,176} +{44,82,113,134,188} +{13,55,65,99,150} +{25,73,130,192} +{88,120,193} +{79,123,153,175} +{24,158,162} +{52,53,81} +{5,32,78,102} +{73,97,111,151} +{71,72,102,151} +{5,61,73,85,129,151} +{66,177} +{26,77,139,152} +{46,117} +{55,72,122,148,157,174} +{3,53,76,184,196} +{34,36,41,61,194} +{8,153,163,182} +{51,59} +{113,115,149} +{54,57,78} +{39,137} +{75,81,93} +{5,30,44,80,86,126} +{68,107,128,160,179} +{98,108,162} +{55,126} +{24,54,121,122} +{75,90} +{10,83,139} +{16,120,148} +{97,175} +{53,70,71,120,135,189} +{9,110,123,150} +{24,42,44,96,138,170} +{17,61} +{23,65,110,135,155,157} +{19,59,139} +{50,65,127,179} +{15,138,152,162} +{15,34} +{25,29,63,135,161} +{47,113,123,129,163} +{25,138,157,184} +{50,92,199} +{110,116} +{15,36,134,145,165,182} +{4,75,82,175} +{24,49,63,89,128} +{174,182} +{103,116,119} +{101,125,180,192} +{47,66,113,127,148} +{15,60,118} +{20,51,90,91,117} +{25,72,146,199} +{34,93,199} +{31,71,106,115,186} +{1,10,119,144,188,197} +{49,80,185} +{134,178,188} +{42,67,170,172} +{13,43,91,91} +{13,31,48,98,155,158} +{37,44,70,76,141,160} +{50,60,72} +{51,65,166,188} +{11,103,129,144} +{136,167,181} +{165,178} +{34,107} +{54,120} +{33,132,136,165,178} +{60,79,119,127,187,197} +{27,31,130,132} +{125,129} +{97,111} +{71,171,187,191} +{68,91,94} +{94,119,159,178} +{2,29,51,173} +{37,61,97,113,147} +{11,35,79,91} +{67,71} +{4,20,103,107,169,179} +{35,77} +{71,94} +{29,31,67,101,172,174} +{52,122} +{87,125} +{129,142,164} +{13,30,85,139} +{17,57,65,170,179} +{46,65,151,167,192,197} +{31,78,132,136,158} +{38,161} +{15,101,111,134} +{42,118,139,142,178} +{57,95,132,134} +{5,42,116,152,173,192} +{144,199} +{38,70,77,143,175,188} +{38,84,93,149} +{56,98,153,165,170,191} +{1,52,112,112,131,145} +{16,132,150,184} +{14,60,111,153} +{49,109,112,165} +{69,136,152} +{59,90,94,158,168} +{42,47} +{18,194} +{33,70,94,167,175,177} +{40,57,125,138,159} +{3,10,31} +{2,5,8,26,141,181} +{27,29,142,175,186,195} +{31,49,99,120} +{109,123} +{21,76,112,119,124} +{41,49,146,173} +{101,173} +{49,73,85,89,179} +{22,36,154,192} +{136,163} +{111,165} +{94,128} +{81,167} +{35,165} +{41,109,119} +{13,74,80,114} +{72,106,189} +{65,172} +{30,31,35,52,63} +{80,116} +{0,149} +{139,189} +{0,65,107,153,179} +{15,40,46,51,75,160} +{12,28,48,79,105} +{76,98,146,157,180} +{45,62,79,83,113,155} +{130,162,184} +{78,140,145,181,196,198} +{108,168} +{3,13,14,15,77} +{22,29,68,117,142,143} +{67,110,122,167,183} +{22,25,58,93,143,151} +{53,82,170} +{1,18,50,98,108,174} +{58,140} +{49,179,196} +{109,171} +{38,82,132,183} +{32,151,175} +{53,90,106,169,187} +{99,136,141,146,171} +{27,108,111,155,192} +{28,77,86} +{11,109,118,149,154,183} +{7,74,122,137,185} +{70,110,151,154,175} +{7,48,88,181,181,182} +{97,101,105,123,139,156} +{19,139} +{17,107,134} +{63,64,178} +{100,133,143} +{64,173} +{1,88,109,120,145,160} +{113,198} +{84,112,121,184} +{90,185,193} +{91,135,155,185} +{56,191} +{14,15,48,61,92,171} +{18,139,152,199} +{16,80,107,125,144,166} +{8,92,112,173,176} +{27,196} +{9,169,183,190} +{20,29,40,98,106,182} +{77,115,149,181} +{31,65} +{7,29,62,90,157,178} +{10,33,79,186} +{42,74,113,178,192} +{17,86,88,118} +{27,58,104,122,166} +{16,97,102,105,192} +{16,59,115,127} +{27,56,60} +{104,175} +{52,84} +{127,137} +{7,13,18,81,139,140} +{11,31,81,150,189} +{44,55,107} +{45,58,127,137} +{70,76,80,93,145} +{27,60} +{40,76,172} +{7,123,192} +{55,170} +{61,137,137,184,187} +{49,50,190} +{99,126,152,164} +{56,79,88,98,132} +{45,74,119,123,158,175} +{66,96} +{100,114} +{62,84,111,122} +{8,22,141,172,181} +{70,141} +{3,48,106,193} +{33,114,168,174,183} +{46,186,194} +{58,71,82,122,190} +{60,67} +{14,30,132,144,174} +{9,113,124} +{11,14,29,63,110,182} +{4,64,102,168,178} +{90,108,110,160,165,199} +{44,86,191} +{6,19,84,125,125,156} +{53,105,122,154,175,190} +{83,177,183} +{96,103,181} +{38,156} +{2,6,60,116,131} +{12,144} +{13,73,93,132} +{142,167} +{37,61,71,75,121,144} +{32,43,146} +{41,59,144,176} +{11,14,44,54,92,177} +{37,198} +{39,80,81,104,138,193} +{13,73,92,127,149,194} +{34,57,69,104,118,186} +{7,48,84,96,108} +{32,41,64,111} +{108,131,150,174,195} +{50,53,184,191} +{8,32} +{26,76,88} +{4,50,100,134,134} +{36,40,148,158,177} +{7,16,57,59} +{35,96,113,129,167} +{46,63,128,163} +{8,46,94,97,105,178} +{12,70} +{45,93,134,135,188,195} +{11,52,76,103,131,192} +{19,45,57,119,123,136} +{19,62} +{1,49,64,197} +{0,42,60,102,134,147} +{102,152,156,160} +{51,54,129} +{50,68,71,72,170} +{0,11,184} +{19,105} +{144,185,191} +{17,51,76,98,118,135} +{52,64,143,171} +{1,46,62,74,81} +{8,36,129} +{5,25,96,113,146,152} +{19,28,59,110,131,142} +{7,18,176,179} +{17,21,48,63,121} +{34,79,81,85,152,155} +{8,82,104,122,139,193} +{34,50,128,140,175} +{51,173} +{48,128,138} +{126,129,178} +{42,51,61,141,170,180} +{59,91,144} +{64,74,118,170,191} +{12,55,116,157,159} +{97,157} +{32,34,102,105,178} +{36,103,125} +{15,36,184} +{6,13} +{0,100,144,185,198} +{32,47,64,66,118,143} +{23,112,117} +{34,44,47,81,124,135} +{21,49,115} +{29,158} +{34,114,127,151} +{111,199} +{23,53,76,113,122,123} +{89,113,117,137} +{52,76,126,155,164} +{4,48,78,114,147,179} +{27,56,151,191} +{3,183} +{30,41,72,145} +{15,41,152,177,196} +{44,58,124,164,177} +{9,51,70,174} +{13,18,81,136,178} +{85,139,142} +{12,62,118,156} +{50,142,149,175} +{35,38,99,100,128} +{53,54,92,123,153,160} +{121,133} +{12,63,117,148,149,187} +{88,153,170,192,195} +{22,51,67,104,141} +{186,198} +{39,40,82,159,189} +{59,74,149} +{88,99,136,145,191} +{5,48,90,120,138,193} +{22,76,155,180} +{118,122,141,176} +{87,104,116,159,172,191} +{63,104,155} +{8,153,168} +{119,141,178,179} +{100,110} +{14,65,164} +{2,92,97,117,188} +{47,59,64,141,148,187} +{109,137,139,151,169} +{68,78,156} +{37,39,103,183,190,194} +{50,58,74,180} +{12,121,155,175} +{26,43,97} +{102,159,161} +{3,138,163,179} +{55,69,78,164} +{67,87,136} +{67,150} +{74,113,199} +{103,126,187} +{39,141,155} +{6,19,25,75,157} +{10,49,71,105,114,154} +{3,24,35,54,88} +{16,25,73,114,181,191} +{2,2,63,154} +{68,74,107,187,199} +{13,235} +{40,122,203,232,233,235} +{115,152,193,202,242} +{3,50,86,111,248} +{25,66,181,188,279} +{80,116} +{38,83,106,119,134} +{29,63,203} +{7,27,186,200,201} +{88,92,94,272,295} +{35,68,136,158} +{148,225,293} +{1,87,195} +{48,100,203} +{0,35,61,91,280} +{130,160,168,216} +{4,104,148,164} +{35,40,91,145,155,214} +{46,107} +{21,276} +{42,143,150,238,291} +{64,70,140,165,228,257} +{0,148,197} +{72,131,195,202,251,270} +{99,195,224,264,292} +{5,184,186,243} +{93,132,137,148,228,251} +{66,125,198,211,285} +{29,79,180} +{41,60,65,66,254} +{4,69,79,207} +{113,182,203,252,259,298} +{10,20} +{99,200,276} +{109,262} +{4,87,193,207,220,273} +{30,183,215} +{7,138,202,215,217} +{25,79,194,203,260} +{128,178} +{62,152,211,279} +{57,99,204,280} +{41,59} +{18,52,200} +{81,132,190,275} +{89,158} +{32,72,122,228,245,249} +{24,72,196,233,299} +{0,5,46,122,213} +{197,242} +{43,105,241,272} +{74,118,158,173,208,288} +{145,149,197,238,252,297} +{32,39,189} +{98,240} +{65,140,149,197,203,204} +{103,225,266} +{84,277,283} +{35,246} +{10,101,239} +{40,75,192,253} +{106,152,247,272,287} +{50,293} +{85,134} +{59,204} +{54,64,88,269,286} +{4,92,111,121,154,182} +{80,163,202,234,277,298} +{129,147,158,196,283,290} +{49,144,232,293} +{20,29,226,244,274} +{64,101,185,189,234,268} +{23,157} +{56,93,133} +{9,57,241,289} +{50,124,181,194,238} +{11,38,67,69,213} +{149,220} +{168,189,267} +{34,133,235,264,284} +{81,239,241,260} +{35,78,80,201,262,297} +{0,196,285} +{71,108,239,258,277,278} +{4,94} +{77,132,140,251} +{11,78,132} +{43,145,188} +{97,144,148,161,254} +{109,132} +{48,83,189,242} +{115,176,276} +{162,210} +{88,109,136,153,154,159} +{265,280} +{74,86,195} +{17,112,188,213,231,266} +{36,136,160,218,239} +{179,273} +{79,118,136,154,200,259} +{161,212} +{24,98,178} +{161,187} +{45,169,227,236} +{218,253} +{10,18,74,258} +{70,199,210,213,285,291} +{12,50,69,92,184,186} +{130,131,163,295} +{198,239,297} +{49,86,125,176,234,282} +{7,129,146,223,269} +{144,173} +{30,52,133,228} +{21,88,176} +{5,70,299} +{37,69,285} +{14,17,45,72,99,197} +{125,196} +{30,220} +{55,103,127,251} +{108,114,156,200,207,217} +{7,195,250} +{64,111,193,202,236} +{92,115,232,233,240} +{22,232,260} +{18,44,191,253,294} +{40,158} +{86,92,103,154,207,294} +{33,177,191,223,235} +{65,116,158,253} +{49,125,152,194} +{100,149,191,266,288} +{13,64,103,254,283} +{42,75,80,103,155} +{77,128,198,280} +{118,218,287} +{0,36,52,101,148} +{1,64,181,201,221} +{6,44,47,71,150,225} +{13,85,88,167} +{31,40,69,91,99,281} +{60,115,157,224,252,273} +{30,87,200,270,285} +{171,293} +{24,33} +{59,69,74,118,190,216} +{147,258,288} +{62,73,219,232,266} +{50,74,225,238,271} +{6,88,115,185,205,262} +{97,230} +{76,76,150,211,228,262} +{134,195} +{104,235} +{38,41,204} +{64,71,124} +{44,63,111,231} +{186,188} +{5,132,225} +{113,286} +{43,161,276} +{8,294} +{18,90,105,169} +{213,213} +{29,45,161,289} +{79,152} +{10,110,162,177,217,238} +{63,98,192,244} +{118,147,187,281} +{5,15,36,94,263} +{40,81,220} +{29,74,76,157,162,206} +{11,28,53,68,126,222} +{73,73,181,239} +{36,60,164} +{16,47,82,152,167,289} +{149,149,219,268,294} +{97,169} +{32,160,210,257} +{32,69} +{7,63,73,195} +{54,110} +{61,75,135,270} +{22,43,127,174,184,208} +{106,113,174} +{0,70,90,239} +{191,260} +{43,80,168} +{25,54,257,263} +{118,213} +{110,207,220,251,287} +{126,139,161,248,252} +{51,79,116,132,190,291} +{183,199,200,254} +{86,233} +{105,109,176,211} +{12,109} +{3,65,158} +{21,86} +{12,15,191} +{181,223,224,256,259,276} +{112,191,219,232,239} +{51,215} +{36,46,278} +{68,75,169,228,244,270} +{10,16,52,172,189,274} +{177,191,197,209,222,282} +{41,119,190,202} +{128,277,292,298} +{34,38} +{22,36,81,117} +{81,161,248,279} +{75,85,103,149,190,211} +{127,279} +{50,74,152} +{122,168,209,240,276,282} +{66,102,208,239,291} +{9,113} +{72,199,237} +{110,112,135,141,270} +{26,109,130,159,291} +{108,206} +{2,289} +{63,238} +{4,57,104,119,142,214} +{46,97,239} +{210,297} +{207,268} +{13,64,80} +{62,109,171,195,232} +{11,260,262,276,292} +{21,75,78,80,140,226} +{38,56} +{122,251,297} +{108,180,213} +{57,58,135,231,233} +{75,136,185,211} +{52,109,122,174,178,255} +{65,91,234,249} +{5,24,53,218} +{90,211,246} +{106,242,260} +{61,136} +{49,87,177,280} +{38,89,104,189,297} +{43,76,293,298} +{182,255,289} +{25,57,64,272} +{23,122,149} +{49,50,129,153} +{183,188,204} +{27,164,226,230} +{0,13,67,145,160,259} +{22,32,43,85,105,124} +{20,199} +{31,119} +{14,16,152,158,196} +{5,59,91,202,217,280} +{100,128,187} +{20,193,214,258,272} +{17,27,55,151,177,219} +{53,55,63,208,213,230} +{15,160,258,260} +{71,147,235,258} +{26,49,173,234,271} +{50,52,58,167,257} +{15,154,213,232} +{6,35,86,94,286} +{0,4,83,262,281} +{93,148,284} +{28,165,262,290} +{18,99,160,266} +{63,223,291,295} +{103,154,180} +{12,110,144,221} +{9,158,203} +{20,207,275} +{9,20,48,88,120,289} +{67,110,133,151,225,297} +{71,102} +{168,208} +{48,137,163,164,280,287} +{90,209} +{28,244} +{107,224,293} +{86,206} +{8,113,147,165,285,286} +{7,159,160,237} +{0,66,87,146,225,294} +{58,100,112,124,189} +{13,108} +{121,168,216,253} +{147,242,282} +{236,240} +{21,28,83,103,166} +{30,88,108,280,295} +{23,136,298} +{125,290} +{140,249,276,277} +{49,81,135,147,164,267} +{28,63,198,297} +{30,101,216,232,267,287} +{54,195,204,223,236,251} +{27,176,179,204,264,291} +{136,164,172,273} +{43,67,81,121,277} +{128,131,256,269} +{176,219,289} +{127,175,259} +{35,94,153,177,222,253} +{29,154,178,240,260} +{165,176,201,243,259} +{17,298} +{29,203,232,241,289} +{107,136,153,238} +{49,198} +{68,179,202,253} +{157,178} +{23,199,287} +{131,228} +{19,19,39,111,138,277} +{49,86,178,194,223,226} +{114,201} +{149,282} +{109,147,150,176,209,229} +{122,131,167,228,258} +{5,40,120,154,266} +{135,207,238,263} +{75,128} +{80,117,296} +{60,82,122,131,138} +{57,146,159,233,244,278} +{15,80,157,182,244,272} +{114,116,160,176,287} +{10,133,279} +{27,115,126,293} +{89,161} +{95,120,218} +{26,269} +{109,281} +{53,62,103,107,118,239} +{185,186,227,252} +{3,125,146,161,288} +{171,245,256,283} +{23,153,201,238} +{0,82,93,218,242} +{101,124,137,150,194} +{21,96,104,201,244,266} +{88,121,147,155,173,225} +{24,106,112,193} +{26,67,115,212,283} +{23,120,280} +{45,99} +{30,66,136,199} +{17,213} +{14,37,55,103,265} +{52,258,284} +{119,213,272,274,285} +{43,45,105,254,288} +{64,81,123,126,164,292} +{88,229,260} +{25,117} +{7,149,197,227,258} +{74,83,240,246,284,292} +{2,4,63,103,115,289} +{92,239} +{12,26,130,228,265} +{53,99,131,142,164,291} +{63,248,259,283} +{186,215,282} +{67,110,160} +{166,191} +{33,156,224} +{152,166,190,250,297} +{123,126,153,199,204} +{49,70,199,238,238,289} +{14,18,65,74,146,235} +{63,77,172,180,186,225} +{1,48,105,170} +{37,56,113,133,196} +{193,261,266} +{190,273} +{38,129,261} +{251,252,253,254,275,296} +{249,275} +{167,205,266} +{27,152,256} +{19,72,248} +{40,73,141,249} +{105,197} +{156,243,277,282} +{165,168,227,298} +{8,31,202,271} +{10,101,109,167,236,277} +{33,91,165,192,206,211} +{102,122,232} +{190,239,283} +{160,185} +{2,13,65,70} +{11,68,170,192,229,284} +{66,90,228,237} +{1,6,92,99,222,242} +{42,128,133,207,289} +{12,100,164,191} +{26,31,120,176,204,220} +{13,39,95,105,120,182} +{114,120,295} +{31,34,55,181,197,235} +{24,52,64,80,142} +{3,49,148,255,268} +{132,175,254} +{32,71,141} +{112,116,186,270,271} +{64,106,209,228,297} +{128,268} +{107,208,299} +{151,173,187,192,213} +{3,296} +{20,31,135,153,289} +{138,193,212,269,277,288} +{73,92,130,295} +{73,80,105} +{50,96,138,199,265} +{4,7,8,183,260,267} +{66,71,118,145} +{15,63,116,160,175,181} +{88,217} +{56,69,106,106,127,274} +{84,205} +{83,101,241,269} +{21,254} +{22,32,83,150,293} +{198,221} +{30,46,95,179,197} +{46,85,208} +{56,112,236} +{71,217} +{31,57,145,253} +{34,133,170} +{48,53,119,187,268,287} +{111,203,229,239} +{62,136} +{49,54,187,254,298} +{20,26,148,159,190,286} +{3,13,193,252,284} +{40,137,154,167,248,259} +{3,47,242,278} +{77,100,143,232} +{51,130} +{66,90,148,220,242,273} +{143,151,211} +{10,23} +{21,30,179} +{17,47,105,156,193,213} +{0,23,25,125,144,146} +{179,209} +{79,113,117,192} +{5,53,216,275,285} +{187,197} +{22,68,218,221} +{0,71,78,110,120,173} +{46,97,117,149,253,286} +{10,20,129,162,171,195} +{60,97,130,163,190} +{57,145,179,283} +{99,274} +{151,161,228,251} +{3,177,192,286} +{21,81,142} +{180,283} +{13,102,131,149,246} +{19,99,132,162,167,257} +{15,86,188,260} +{203,251,281} +{5,45,138,155,157} +{1,2,4,213,278} +{21,123,208,219,263,267} +{36,106,181,231,238} +{103,120,168,184,224,287} +{53,104,139,251} +{1,91,141,202,268} +{75,115,216,253} +{56,167,268,296} +{66,158,235,249} +{82,124,198} +{56,67,112,140,170,176} +{16,75,266} +{38,165,200,219,291,297} +{86,151,229,241,275} +{0,57,141,176,229,258} +{18,72,164,195,235} +{94,282} +{83,139,242,269,294} +{9,44,145,251,272} +{132,203,249,282} +{7,41,170,254} +{6,153,193,291} +{18,134,137,227,261} +{14,36,115,124,172,229} +{54,206} +{49,91,131,185,204} +{7,242} +{41,57,161} +{93,224,241,288} +{119,288} +{90,99,117,196,296} +{67,85,154} +{147,169,216,264} +{79,92,164} +{19,120,132,197,267} +{76,264} +{30,133} +{27,37,93,138,218} +{152,155,244} +{41,149,182,259} +{29,178,224} +{115,201,268} +{141,166,253,282} +{3,65,125,245,264} +{6,150,159,202,206,277} +{217,276} +{28,96,144,193} +{7,59,190} +{144,217} +{10,79,96,100,126,222} +{7,61,253} +{14,69,263} +{3,30,63,125,186,277} +{2,10,79,100,223} +{131,131,239} +{116,195,199,240} +{87,99,158} +{52,180} +{7,12,140,208,275} +{65,67,83,280} +{4,52,125,126,137,176} +{9,48,79,203,217,243} +{43,206,251} +{19,112,196,263,266} +{29,70,256} +{161,236,258} +{8,25,42,97,291} +{63,144,242,271} +{7,17} +{1,85,250} +{104,244,250} +{18,22,31,99,266,281} +{51,138,237,268,288} +{8,40,91,221,273} +{0,176,230,249,254,255} +{44,140,176,194,197} +{56,197,264} +{229,246,283} +{53,128,173,233,282} +{45,193,221} +{21,80,286} +{4,18,267} +{15,97,220} +{62,70,83,147,149,244} +{120,134,159,174,250} +{116,269} +{23,108} +{10,91,239} +{7,128,142,243,286} +{134,201,245,275,278} +{13,208,227,288} +{30,78,85} +{107,179} +{31,59,153,217,240,298} +{27,130,233,282,286} +{15,59,136,262} +{85,186,233} +{10,152,165,181,181} +{137,183} +{40,56,125,256,265,280} +{12,22,120,183} +{62,229} +{38,59,81,113,261} +{67,194,229} +{7,173} +{37,43,296} +{59,162,285} +{171,200,213,213} +{116,123,209,234,277} +{52,175} +{189,213} +{30,94,99,228,238} +{46,101,154,260,272,274} +{30,32,59} +{65,172,292} +{18,22,131,170,271} +{2,53,88,104,264,265} +{60,194,288} +{15,108,121,161,201} +{40,85,173,195,201,221} +{54,86,107,174,287} +{20,71,190,227} +{16,46,66,175,197,252} +{130,243,252,282} +{142,219,266,272} +{14,202,204,231,241,276} +{161,172,212,222} +{15,183,275} +{83,270} +{67,204} +{65,184,264} +{73,119,183,190,242} +{53,287} +{24,171} +{72,220,220} +{101,136,176,204,224,280} +{39,47,282} +{106,162,238,252} +{23,242,247,265} +{98,108,189,209,273} +{122,245,270} +{109,127,128,244,299} +{41,162,186,191} +{60,196} +{0,123,129,213,248} +{29,79,89,91} +{172,298} +{122,140,162,228,263,268} +{2,116,247,294} +{6,138} +{17,98,287} +{53,166,187,219,248,296} +{15,26,90,175,196} +{184,193,198} +{17,69,76,105,183,264} +{56,101,110} +{15,108,139,168,272} +{5,71,104,141} +{136,179} +{72,189} +{54,79,208} +{98,113,150,184,190,246} +{37,69,132,210,285} +{1,29,45,74,109,145} +{11,72,133,149,216} +{34,57,84,212,280} +{131,211,294} +{70,84,173} +{193,213,230,266,285,299} +{57,94,163,182,227} +{44,133,143} +{31,32,211} +{130,142,165,188,194,231} +{52,61,139,226,239,287} +{7,103,157} +{155,224,230} +{127,135,139} +{77,237,294} +{10,213,278} +{28,90,185,274} +{59,105,282,297} +{39,128,174,268} +{32,158,215} +{24,145,189,213,278} +{78,148,230,263} +{42,68,93,160,287,299} +{4,12,70,91,191,237} +{20,294} +{45,53,77,113,211,240} +{232,237} +{125,152,284} +{58,81,155,215,296} +{4,8,44} +{1,52,102,128,184,218} +{185,199,226,299} +{10,178,262,285} +{80,95,230,240,266} +{4,5,213} +{156,187,271,298} +{88,298} +{109,233,290} +{47,65,91,105,249,269} +{97,129} +{46,92,207} +{2,163,249,259,291} +{89,102,140,158,231} +{162,184,283} +{36,213} +{163,259} +{47,220,250} +{37,89,105,124,143,198} +{3,71} +{142,165,190,256,269,269} +{152,256} +{27,49,191,198,220,285} +{71,73,87,189,260} +{11,54,90,106,130,216} +{193,245,252} +{2,8,57,91,163,184} +{18,171,283} +{28,41,110,112} +{5,57} +{137,262,285} +{19,57,156,229,269} +{138,179,190,199,281} +{35,98,196,242} +{122,152} +{83,132,181,212,280,288} +{219,298} +{57,88,103} +{5,203} +{98,156,266} +{10,45,72,169,211} +{45,101,156,214,269} +{68,73,81} +{16,127,259} +{9,32,246} +{66,173,261,261,274} +{17,115,157,169,251} +{49,158} +{25,37} +{2,73,103,178,194,236} +{238,269,273} +{162,178,276} +{48,52,160,237,288} +{54,82,130,135,169,275} +{29,142} +{205,249,253,275,291} +{60,76,84,115,126} +{48,108,153,213,231} +{23,124,175,210,226,293} +{9,181} +{20,99,112,166,201,242} +{102,150,201} +{41,98,240,244,260} +{7,44,98,293} +{0,125,177,283} +{28,118,124,148,241,290} +{73,91,122} +{9,72,109,130,202,290} +{70,111,120,160,216,262} +{59,175,296} +{2,201} +{83,297} +{76,293} +{83,127,136,242,275,285} +{169,190,195} +{83,122,186,189,217,229} +{98,210,229} +{117,133} +{74,294} +{6,31,59,143,156,273} +{98,180,241} +{26,52,114,243} +{112,240} +{104,217} +{148,162,259,279} +{92,101,150,226,272,295} +{55,86,118,202,237,275} +{81,203} +{79,126,177,265} +{57,193} +{169,240,244} +{21,171,190,250,263} +{23,37,215,235} +{40,54,240,286} +{105,177,190,276,285} +{44,45,122,151} +{28,31,187} +{127,135,211} +{5,13,150,194,259} +{136,181,280} +{20,147,158,189,200} +{15,83,88,128,169} +{10,14,25,26,150,158} +{42,101,172,205} +{85,185,226,236,271} +{34,127,188,250,268} +{27,143} +{26,48,99,110,117,207} +{22,56,190,269,287} +{200,278} +{70,134,138,204,216,298} +{175,219,297} +{99,273} +{206,216} +{23,214} +{131,140} +{11,140,240} +{73,148} +{7,66,125,210} +{2,61,92} +{0,137} +{143,188,265} +{177,238} +{0,93,163,229} +{35,49} +{8,8,111,144,165} +{99,278} +{21,44,71,224,252,270} +{119,150,175,233,245,294} +{15,87} +{84,211,217,225} +{20,41,87,123,124,299} +{62,120,169} +{37,43,92,175,206,222} +{95,168,180,250,269,296} +{60,228,278,285} +{173,195,232,276} +{1,2,139,256,278} +{51,119} +{212,238,291} +{120,172,292} +{138,279} +{251,261} +{151,181,278,296} +{163,207,220,289,295} +{89,278,290} +{24,137,157,206,271,278} +{7,63,83,89,155,189} +{2,5,172,195,215,260} +{243,281} +{60,125} +{74,87,222,236} +{45,70,159,194} +{69,159,250} +{150,214,296} +{101,158,250} +{56,134} +{57,87,160,167,247,285} +{123,269} +{235,242} +{79,95,115,167,287} +{31,56,132,244,276} +{25,218,241,241} +{57,82,151,170,204} +{69,103,288} +{88,138,154,292} +{14,98,138,227,245,249} +{175,222,274} +{38,139,193,208,277} +{79,141} +{5,77,197,209} +{15,37,77,110,116} +{26,226} +{68,93,101,140,233} +{53,96,170,192,290} +{29,89,102,216,220} +{11,85,136,239} +{158,180,195,200,226} +{10,49,118,137,172} +{144,172,183} +{14,176,188,215,272} +{42,97,125} +{114,166} +{52,61,162,171,249} +{140,195,242} +{59,99,233} +{31,76,136,181,187} +{81,112,157,168,271,294} +{8,35,44,48,190,297} +{145,195,201} +{160,248,291} +{94,270,285} +{116,139,225} +{111,131,140} +{158,277} +{59,229,257} +{25,47,99,123,239} +{8,36,205,274,295} +{132,152,178,192,235} +{19,40,96,204} +{7,77} +{211,282} +{26,100,180,244,281,296} +{200,212,286} +{5,94,151,290} +{75,80,128,179,269,269} +{7,111} +{7,26,69,158,269,276} +{7,36,74,94,171,215} +{2,62,65,93,124,271} +{78,96,109,189} +{182,197,280,298} +{17,78,82,85,85,208} +{6,122,155} +{14,33,130} +{1,21,167,169} +{49,85,158,175,213} +{59,194} +{125,132,259,285} +{20,38,81,89,234,274} +{106,140,156,287} +{57,125} +{53,103,158,204,234,267} +{0,49,160,189,235} +{34,115,142,207} +{162,173,181,190,298} +{11,76,116,166,191} +{2,87,99,236,279} +{40,203} +{2,33,39,215,254} +{53,69,83,224,228} +{79,136,183,216,226,227} +{10,109,137,163,240} +{24,126,141} +{69,255} +{103,138,230,246,259,283} +{136,290} +{13,34,78,145,166,242} +{38,74,83,242,294} +{54,248,273} +{107,162} +{50,170,176,191,207,275} +{32,134,166,288,292} +{163,167,186,274,291,296} +{31,86,123,156,160} +{114,133,136,176,281,290} +{105,147,211} +{124,151,179,222,299} +{87,101} +{145,169,181,205,247} +{6,266} +{26,33,52,56,106,116} +{19,21,65,89,104,168} +{164,181,208} +{36,67,92,116,248} +{145,200,247} +{155,215} +{49,212} +{29,57,105,117,131} +{2,13,68,128,139,140} +{193,273,273} +{3,78,105,111,297} +{49,142,244} +{32,259} +{161,205} +{96,146,179,259} +{44,45,211,233} +{56,91,146,166,285} +{87,107,120,262,299} +{76,160,276,297} +{248,266} +{5,12,188,240,247} +{164,206,293} +{15,18,60,163} +{53,134,172,230,287,290} +{117,137,146,153,155} +{72,270} +{171,251} +{80,125,137,141,169} +{52,108,200,219,225,271} +{29,78,106,221} +{21,74,110,273} +{28,88,98,170} +{83,104} +{12,152} +{7,69,143,246,265,269} +{62,106,157,200} +{113,260,272,272,294} +{16,35,80,121,165,176} +{96,154,172,198,263} +{29,53,109,128,129,195} +{131,230,271,273,295,299} +{53,160,208,231} +{23,180,208,249,272} +{45,208,264} +{14,29,169} +{116,147,272} +{7,193,237,271} +{158,198,253} +{41,60,71} +{110,133,200,249} +{24,159,255} +{26,39,61,114,218,229} +{141,286,299} +{74,278} +{67,71,155} +{151,257,284} +{13,28,72,131,206} +{60,152,275,295} +{88,105,184,185} +{85,190,205,256,283,285} +{202,285} +{14,92,160,200,246,279} +{42,95,157,195} +{50,99,224,276} +{32,97,101,122} +{66,85} +{19,146,180,242,269,286} +{24,86,247,274} +{54,264,270,284} +{72,77,85,124,127,285} +{47,249} +{25,73,102,237} +{33,68,84,117,120} +{29,62,172,240,242,273} +{42,140,182,248,261,282} +{118,228,284} +{1,89,158,294} +{29,89,122,155,208,283} +{173,208,229} +{6,22,142,267,299} +{22,122,173,245,293} diff --git a/contrib/intarray/expected/_int.out b/contrib/intarray/expected/_int.out index 62748cefaf..4cde92ce56 100644 --- a/contrib/intarray/expected/_int.out +++ b/contrib/intarray/expected/_int.out @@ -8,7 +8,7 @@ CREATE TABLE test__int( a int[] ); SELECT count(*) from test__int WHERE a && '{23,50}'; count ------- - 345 + 403 (1 row) SELECT count(*) from test__int WHERE a @ '{23,50}'; @@ -21,7 +21,7 @@ CREATE INDEX text_idx on test__int using gist ( a gist__int_ops ) with ( islossy SELECT count(*) from test__int WHERE a && '{23,50}'; count ------- - 345 + 403 (1 row) SELECT count(*) from test__int WHERE a @ '{23,50}'; @@ -35,7 +35,7 @@ CREATE INDEX text_idx on test__int using gist ( a gist__intbig_ops ) with ( islo SELECT count(*) from test__int WHERE a && '{23,50}'; count ------- - 345 + 403 (1 row) SELECT count(*) from test__int WHERE a @ '{23,50}'; -- 2.40.0