diff options
Diffstat (limited to 'contrib/intarray')
-rw-r--r-- | contrib/intarray/Makefile | 12 | ||||
-rw-r--r-- | contrib/intarray/README.intarray | 100 | ||||
-rw-r--r-- | contrib/intarray/_int.c | 2219 | ||||
-rw-r--r-- | contrib/intarray/_int.sql.in | 437 | ||||
-rwxr-xr-x | contrib/intarray/bench/bench.pl | 104 | ||||
-rwxr-xr-x | contrib/intarray/bench/create_test.pl | 73 | ||||
-rw-r--r-- | contrib/intarray/data/test__int.data | 7000 | ||||
-rw-r--r-- | contrib/intarray/expected/_int.out | 377 | ||||
-rw-r--r-- | contrib/intarray/sql/_int.sql | 84 |
9 files changed, 0 insertions, 10406 deletions
diff --git a/contrib/intarray/Makefile b/contrib/intarray/Makefile deleted file mode 100644 index 7cb06da2ac8..00000000000 --- a/contrib/intarray/Makefile +++ /dev/null @@ -1,12 +0,0 @@ -# $Header: /cvsroot/pgsql/contrib/intarray/Makefile,v 1.8 2001/09/06 10:49:29 petere Exp $ - -subdir = contrib/intarray -top_builddir = ../.. -include $(top_builddir)/src/Makefile.global - -MODULES = _int -DATA_built = _int.sql -DOCS = README.intarray -REGRESS = _int - -include $(top_srcdir)/contrib/contrib-global.mk diff --git a/contrib/intarray/README.intarray b/contrib/intarray/README.intarray deleted file mode 100644 index f0138a14842..00000000000 --- a/contrib/intarray/README.intarray +++ /dev/null @@ -1,100 +0,0 @@ -This is an implementation of RD-tree data structure using GiST interface -of PostgreSQL. It has built-in lossy compression. - -Current implementation provides index support for one-dimensional array of -int4's - gist__int_ops, suitable for small and medium size of arrays (used on -default), and gist__intbig_ops for indexing large arrays (we use superimposed -signature with length of 4096 bits to represent sets). - -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: - -October 1, 2001 - 1. Change search method in array to binary -September 28, 2001 - 1. gist__int_ops now is without lossy - 2. add sort entry in picksplit -September 21, 2001 - 1. Added support for boolean query (indexable operator @@, looks like - a @@ '1|(2&3)', perfomance is better in any case ) - 2. Done some small optimizations -March 19, 2001 - 1. Added support for toastable keys - 2. Improved split algorithm for intbig (selection speedup is about 30%) - -INSTALLATION: - - gmake - gmake install - -- load functions - psql <database> < _int.sql - -REGRESSION TEST: - - gmake installcheck - -EXAMPLE USAGE: - - create table message (mid int not null,sections int[]); - create table message_section_map (mid int not null,sid int not null); - - -- create indices -CREATE unique index message_key on message ( mid ); -CREATE unique index message_section_map_key2 on message_section_map (sid, mid ); -CREATE INDEX message_rdtree_idx on message using gist ( sections gist__int_ops); - - -- select some messages with section in 1 OR 2 - OVERLAP operator - select message.mid from message where message.sections && '{1,2}'; - - -- select messages contains in sections 1 AND 2 - CONTAINS operator - select message.mid from message where message.sections @ '{1,2}'; - -- the same, CONTAINED operator - select message.mid from message where '{1,2}' ~ message.sections; - -BENCHMARK: - - subdirectory bench contains benchmark suite. - cd ./bench - 1. createdb TEST - 2. psql TEST < ../_int.sql - 3. ./create_test.pl | psql TEST - 4. ./bench.pl - perl script to benchmark queries, supports OR, AND queries - with/without RD-Tree. Run script without arguments to - see availbale options. - - a)test without RD-Tree (OR) - ./bench.pl -d TEST -s 1,2 -v - b)test with RD-Tree - ./bench.pl -d TEST -s 1,2 -v -r - -BENCHMARKS: - -Size of table <message>: 200000 -Size of table <message_section_map>: 268538 - -Distribution of messages by sections: - -section 0: 73899 messages -section 1: 16298 messages -section 50: 1241 messages -section 99: 705 messages - -old - without RD-Tree support, -new - with RD-Tree - -+----------+---------------+----------------+ -|Search set|OR, time in sec|AND, time in sec| -| +-------+-------+--------+-------+ -| | old | new | old | new | -+----------+-------+-------+--------+-------+ -| 1| 1.427| 0.215| -| -| -+----------+-------+-------+--------+-------+ -| 99| 1.029| 0.018| -| -| -+----------+-------+-------+--------+-------+ -| 1,2| 1.829| 0.334| 5.654| 0.042| -+----------+-------+-------+--------+-------+ -| 1,2,50,60| 2.057| 0.359| 5.044| 0.007| -+----------+-------+-------+--------+-------+ diff --git a/contrib/intarray/_int.c b/contrib/intarray/_int.c deleted file mode 100644 index d956543af5f..00000000000 --- a/contrib/intarray/_int.c +++ /dev/null @@ -1,2219 +0,0 @@ -/****************************************************************************** - This file contains routines that can be bound to a Postgres backend and - called by the backend in the process of processing queries. The calling - format for these routines is dictated by Postgres architecture. -******************************************************************************/ - -/* -#define BS_DEBUG -#define GIST_DEBUG -#define GIST_QUERY_DEBUG -*/ - -#include "postgres.h" - -#include <float.h> - -#include "access/gist.h" -#include "access/itup.h" -#include "access/rtree.h" -#include "utils/elog.h" -#include "utils/palloc.h" -#include "utils/array.h" -#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 - -/* - * flags for gist__int_ops, use ArrayType->flags - * which is unused (see array.h) - */ -#define LEAFKEY (1<<31) -#define ISLEAFKEY(x) ( ((ArrayType*)(x))->flags & LEAFKEY ) - -/* useful macros for accessing int4 arrays */ -#define ARRPTR(x) ( (int4 *) ARR_DATA_PTR(x) ) -#define ARRNELEMS(x) ArrayGetNItems( ARR_NDIM(x), ARR_DIMS(x)) - -#define ARRISVOID(x) ( (x) ? ( ( ARR_NDIM(x) == NDIM ) ? ( ( ARRNELEMS( x ) ) ? 0 : 1 ) : ( ( ARR_NDIM(x) ) ? (elog(ERROR,"Array is not one-dimensional: %d dimensions",ARRNELEMS( x )),1) : 0 ) ) : 0 ) - -#define SORT(x) \ - do { \ - if ( ARRNELEMS( x ) > 1 ) \ - isort( ARRPTR( x ), ARRNELEMS( x ) ); \ - } while(0) - -#define PREPAREARR(x) \ - do { \ - if ( ARRNELEMS( x ) > 1 ) \ - if ( isort( 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 64 /* >122 => key will toast, so very slow!!! */ -#define SIGLEN ( sizeof(int)*SIGLENINT ) -#define SIGLENBIT (SIGLEN*BITBYTE) - -typedef char BITVEC[SIGLEN]; -typedef char *BITVECP; - -#define SIGPTR(x) ( (BITVECP) ARR_DATA_PTR(x) ) - - -#define LOOPBYTE(a) \ - for(i=0;i<SIGLEN;i++) {\ - a;\ - } - -#define LOOPBIT(a) \ - for(i=0;i<SIGLENBIT;i++) {\ - a;\ - } - -/* beware of multiple evaluation of arguments to these macros! */ -#define GETBYTE(x,i) ( *( (BITVECP)(x) + (int)( (i) / BITBYTE ) ) ) -#define GETBITBYTE(x,i) ( (*((char*)(x)) >> (i)) & 0x01 ) -#define CLRBIT(x,i) GETBYTE(x,i) &= ~( 0x01 << ( (i) % BITBYTE ) ) -#define SETBIT(x,i) GETBYTE(x,i) |= ( 0x01 << ( (i) % BITBYTE ) ) -#define GETBIT(x,i) ( (GETBYTE(x,i) >> ( (i) % BITBYTE )) & 0x01 ) -#define HASHVAL(val) (((unsigned int)(val)) % SIGLENBIT) -#define HASH(sign, val) SETBIT((sign), HASHVAL(val)) - - -#ifdef GIST_DEBUG -static void -printarr(ArrayType *a, int num) -{ - char bbb[16384]; - char *cur; - int l; - int *d; - - d = ARRPTR(a); - *bbb = '\0'; - cur = bbb; - for (l = 0; l < min(num, ARRNELEMS(a)); l++) - { - sprintf(cur, "%d ", d[l]); - cur = strchr(cur, '\0'); - } - elog(DEBUG3, "\t\t%s", bbb); -} -static void -printbitvec(BITVEC bv) -{ - int i; - char str[SIGLENBIT + 1]; - - str[SIGLENBIT] = '\0'; - LOOPBIT(str[i] = (GETBIT(bv, i)) ? '1' : '0'); - - elog(DEBUG3, "BV: %s", str); -} - -#endif - -/* -** types for functions -*/ -typedef ArrayType *(*formarray) (ArrayType *, ArrayType *); -typedef void (*formfloat) (ArrayType *, float *); - -/* -** usefull function -*/ -static bool isort(int4 *a, const int len); -static ArrayType *new_intArrayType(int num); -static ArrayType *copy_intArrayType(ArrayType *a); -static ArrayType *resize_intArrayType(ArrayType *a, int num); -static int internal_size(int *a, int len); -static ArrayType *_int_unique(ArrayType *a); - -/* common GiST function*/ -static GIST_SPLITVEC *_int_common_picksplit(bytea *entryvec, - GIST_SPLITVEC *v, - formarray unionf, - formarray interf, - formfloat sizef, - float coef); -static float *_int_common_penalty(GISTENTRY *origentry, - GISTENTRY *newentry, - float *result, - formarray unionf, - formfloat sizef); -static ArrayType *_int_common_union(bytea *entryvec, - int *sizep, - formarray unionf); - -/* -** GiST support methods -*/ -PG_FUNCTION_INFO_V1( g_int_consistent ); -PG_FUNCTION_INFO_V1( g_int_compress ); -PG_FUNCTION_INFO_V1( g_int_decompress ); -PG_FUNCTION_INFO_V1( g_int_penalty ); -PG_FUNCTION_INFO_V1( g_int_picksplit ); -PG_FUNCTION_INFO_V1( g_int_union ); -PG_FUNCTION_INFO_V1( g_int_same ); - -Datum g_int_consistent(PG_FUNCTION_ARGS); -Datum g_int_compress(PG_FUNCTION_ARGS); -Datum g_int_decompress(PG_FUNCTION_ARGS); -Datum g_int_penalty(PG_FUNCTION_ARGS); -Datum g_int_picksplit(PG_FUNCTION_ARGS); -Datum g_int_union(PG_FUNCTION_ARGS); -Datum g_int_same(PG_FUNCTION_ARGS); - - -/* -** R-tree support functions -*/ -static bool inner_int_contains(ArrayType *a, ArrayType *b); -static bool inner_int_overlap(ArrayType *a, ArrayType *b); -static ArrayType *inner_int_union(ArrayType *a, ArrayType *b); -static ArrayType *inner_int_inter(ArrayType *a, ArrayType *b); -static void rt__int_size(ArrayType *a, float *sz); - -PG_FUNCTION_INFO_V1( _int_different ); -PG_FUNCTION_INFO_V1( _int_same ); -PG_FUNCTION_INFO_V1( _int_contains ); -PG_FUNCTION_INFO_V1( _int_contained ); -PG_FUNCTION_INFO_V1( _int_overlap ); -PG_FUNCTION_INFO_V1( _int_union ); -PG_FUNCTION_INFO_V1( _int_inter ); - -Datum _int_different(PG_FUNCTION_ARGS); -Datum _int_same(PG_FUNCTION_ARGS); -Datum _int_contains(PG_FUNCTION_ARGS); -Datum _int_contained(PG_FUNCTION_ARGS); -Datum _int_overlap(PG_FUNCTION_ARGS); -Datum _int_union(PG_FUNCTION_ARGS); -Datum _int_inter(PG_FUNCTION_ARGS); - -/* -** _intbig methods -*/ -PG_FUNCTION_INFO_V1( g_intbig_consistent ); -PG_FUNCTION_INFO_V1( g_intbig_compress ); -PG_FUNCTION_INFO_V1( g_intbig_decompress ); -PG_FUNCTION_INFO_V1( g_intbig_penalty ); -PG_FUNCTION_INFO_V1( g_intbig_picksplit ); -PG_FUNCTION_INFO_V1( g_intbig_union ); -PG_FUNCTION_INFO_V1( g_intbig_same ); - -Datum g_intbig_consistent(PG_FUNCTION_ARGS); -Datum g_intbig_compress(PG_FUNCTION_ARGS); -Datum g_intbig_decompress(PG_FUNCTION_ARGS); -Datum g_intbig_penalty(PG_FUNCTION_ARGS); -Datum g_intbig_picksplit(PG_FUNCTION_ARGS); -Datum g_intbig_union(PG_FUNCTION_ARGS); -Datum g_intbig_same(PG_FUNCTION_ARGS); - -static bool _intbig_contains(ArrayType *a, ArrayType *b); -static bool _intbig_overlap(ArrayType *a, ArrayType *b); -static ArrayType *_intbig_union(ArrayType *a, ArrayType *b); - -static ArrayType * _intbig_inter(ArrayType *a, ArrayType *b); -static void rt__intbig_size(ArrayType *a, float *sz); - - - -/***************************************************************************** - * Boolean Search - *****************************************************************************/ - -#define BooleanSearchStrategy 20 - -/* - * item in polish notation with back link - * to left operand - */ -typedef struct ITEM { - int2 type; - int2 left; - int4 val; -} ITEM; - -typedef struct { - int4 len; - int4 size; - char data[1]; -} QUERYTYPE; - -#define HDRSIZEQT ( 2*sizeof(int4) ) -#define COMPUTESIZE(size) ( HDRSIZEQT + size * sizeof(ITEM) ) -#define GETQUERY(x) (ITEM*)( (char*)(x)+HDRSIZEQT ) - -PG_FUNCTION_INFO_V1(bqarr_in); -PG_FUNCTION_INFO_V1(bqarr_out); -Datum bqarr_in(PG_FUNCTION_ARGS); -Datum bqarr_out(PG_FUNCTION_ARGS); - -PG_FUNCTION_INFO_V1(boolop); -Datum boolop(PG_FUNCTION_ARGS); - -PG_FUNCTION_INFO_V1(rboolop); -Datum rboolop(PG_FUNCTION_ARGS); - -PG_FUNCTION_INFO_V1(querytree); -Datum querytree(PG_FUNCTION_ARGS); - -static bool signconsistent( QUERYTYPE *query, BITVEC sign, bool leaf ); -static bool execconsistent( QUERYTYPE *query, ArrayType *array, bool leaf ); - -/***************************************************************************** - * GiST functions - *****************************************************************************/ - -/* -** The GiST Consistent method for _intments -** Should return false if for all data items x below entry, -** the predicate x op query == FALSE, where op is the oper -** corresponding to strategy in the pg_amop table. -*/ -Datum -g_int_consistent(PG_FUNCTION_ARGS) { - GISTENTRY *entry = (GISTENTRY *)PG_GETARG_POINTER(0); - ArrayType *query = ( ArrayType * )PG_GETARG_POINTER(1); - StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2); - bool retval; - - if ( strategy == BooleanSearchStrategy ) - PG_RETURN_BOOL(execconsistent( (QUERYTYPE*)query, - (ArrayType *) DatumGetPointer(entry->key), - ISLEAFKEY( (ArrayType *) DatumGetPointer(entry->key) ) ) ); - - /* XXX are we sure it's safe to scribble on the query object here? */ - /* XXX what about toasted input? */ - /* sort query for fast search, key is already sorted */ - if ( ARRISVOID( query ) ) - PG_RETURN_BOOL(false); - PREPAREARR(query); - - switch (strategy) - { - case RTOverlapStrategyNumber: - retval = inner_int_overlap((ArrayType *) DatumGetPointer(entry->key), - query); - break; - case RTSameStrategyNumber: - if ( GIST_LEAF(entry) ) - DirectFunctionCall3( - g_int_same, - entry->key, - PointerGetDatum(query), - PointerGetDatum(&retval) - ); - else - retval = inner_int_contains((ArrayType *) DatumGetPointer(entry->key), - query); - break; - case RTContainsStrategyNumber: - retval = inner_int_contains((ArrayType *) DatumGetPointer(entry->key), - query); - break; - case RTContainedByStrategyNumber: - if ( GIST_LEAF(entry) ) - retval = inner_int_contains(query, - (ArrayType *) DatumGetPointer(entry->key) ); - else - retval = inner_int_overlap((ArrayType *) DatumGetPointer(entry->key), - query); - break; - default: - retval = FALSE; - } - PG_RETURN_BOOL(retval); -} - -Datum -g_int_union(PG_FUNCTION_ARGS) -{ - PG_RETURN_POINTER( _int_common_union( - (bytea *) PG_GETARG_POINTER(0), - (int *) PG_GETARG_POINTER(1), - inner_int_union - ) ); -} - -/* -** GiST Compress and Decompress methods -*/ -Datum -g_int_compress(PG_FUNCTION_ARGS) -{ - GISTENTRY *entry = (GISTENTRY *)PG_GETARG_POINTER(0); - GISTENTRY *retval; - ArrayType *r; - int len; - int *dr; - int i, - min, - cand; - - if (entry->leafkey) { - r = (ArrayType *) PG_DETOAST_DATUM_COPY(entry->key); - PREPAREARR(r); - r->flags |= LEAFKEY; - retval = palloc(sizeof(GISTENTRY)); - gistentryinit(*retval, PointerGetDatum(r), - entry->rel, entry->page, entry->offset, VARSIZE(r), FALSE); - - PG_RETURN_POINTER(retval); - } - - r = (ArrayType *) PG_DETOAST_DATUM(entry->key); - if ( ISLEAFKEY( r ) || ARRISVOID(r) ) { - if ( r != (ArrayType*)DatumGetPointer(entry->key) ) - pfree(r); - PG_RETURN_POINTER(entry); - } - - if ( (len=ARRNELEMS(r)) >= 2 * MAXNUMRANGE) { /* compress */ - if ( r == (ArrayType*)DatumGetPointer( entry->key) ) - r = (ArrayType *) PG_DETOAST_DATUM_COPY(entry->key); - r = resize_intArrayType(r, 2 * (len)); - - dr = ARRPTR(r); - - for (i = len - 1; i >= 0; i--) - dr[2 * i] = dr[2 * i + 1] = dr[i]; - - len *= 2; - cand = 1; - while (len > MAXNUMRANGE * 2) - { - min = 0x7fffffff; - for (i = 2; i < len; i += 2) - if (min > (dr[i] - dr[i - 1])) - { - min = (dr[i] - dr[i - 1]); - cand = i; - } - memmove((void *) &dr[cand - 1], (void *) &dr[cand + 1], (len - cand - 1) * sizeof(int)); - len -= 2; - } - r = resize_intArrayType(r, len); - retval = palloc(sizeof(GISTENTRY)); - gistentryinit(*retval, PointerGetDatum(r), - entry->rel, entry->page, entry->offset, VARSIZE(r), FALSE); - PG_RETURN_POINTER(retval); - } else { - PG_RETURN_POINTER(entry); - } - - PG_RETURN_POINTER(entry); -} - -Datum -g_int_decompress(PG_FUNCTION_ARGS) -{ - GISTENTRY *entry = (GISTENTRY *)PG_GETARG_POINTER(0); - GISTENTRY *retval; - ArrayType *r; - int *dr, - lenr; - ArrayType *in; - int lenin; - int *din; - int i, - j; - - in = (ArrayType *) PG_DETOAST_DATUM(entry->key); - - if ( ARRISVOID(in) ) { - PG_RETURN_POINTER(entry); - } - - lenin = ARRNELEMS(in); - - if (lenin < 2 * MAXNUMRANGE || ISLEAFKEY( in ) ) { /* not comressed value */ - if ( in != (ArrayType *) DatumGetPointer(entry->key)) { - retval = palloc(sizeof(GISTENTRY)); - gistentryinit(*retval, PointerGetDatum(in), - entry->rel, entry->page, entry->offset, VARSIZE(in), FALSE); - - PG_RETURN_POINTER(retval); - } - PG_RETURN_POINTER(entry); - } - - din = ARRPTR(in); - lenr = internal_size(din, lenin); - - r = new_intArrayType(lenr); - dr = ARRPTR(r); - - for (i = 0; i < lenin; i += 2) - for (j = din[i]; j <= din[i + 1]; j++) - if ((!i) || *(dr - 1) != j) - *dr++ = j; - - if (in != (ArrayType *) DatumGetPointer(entry->key)) - pfree(in); - retval = palloc(sizeof(GISTENTRY)); - gistentryinit(*retval, PointerGetDatum(r), - entry->rel, entry->page, entry->offset, VARSIZE(r), FALSE); - - PG_RETURN_POINTER(retval); -} - -/* -** The GiST Penalty method for _intments -*/ -Datum -g_int_penalty(PG_FUNCTION_ARGS) -{ - PG_RETURN_POINTER( _int_common_penalty( - (GISTENTRY *)PG_GETARG_POINTER(0), - (GISTENTRY *)PG_GETARG_POINTER(1), - (float *) PG_GETARG_POINTER(2), - inner_int_union, rt__int_size - ) ); -} - - -Datum -g_int_picksplit(PG_FUNCTION_ARGS) -{ - PG_RETURN_POINTER( _int_common_picksplit( - (bytea *)PG_GETARG_POINTER(0), - (GIST_SPLITVEC *)PG_GETARG_POINTER(1), - inner_int_union, - inner_int_inter, - rt__int_size, - 0.01 - ) ); -} - -/* -** Equality methods -*/ - - -Datum -g_int_same(PG_FUNCTION_ARGS) -{ - ArrayType *a = (ArrayType*)PointerGetDatum(PG_GETARG_POINTER(0)); - ArrayType *b = (ArrayType*)PointerGetDatum(PG_GETARG_POINTER(1)); - bool *result = (bool *)PG_GETARG_POINTER(2); - int4 n = ARRNELEMS(a); - int4 *da, *db; - - if ( n != ARRNELEMS(b) ) { - *result = false; - PG_RETURN_POINTER(result); - } - *result = TRUE; - da = ARRPTR(a); - db = ARRPTR(b); - while(n--) - if (*da++ != *db++) { - *result = FALSE; - break; - } - - PG_RETURN_POINTER(result); -} - -Datum -_int_contained(PG_FUNCTION_ARGS) -{ - PG_RETURN_BOOL( DatumGetBool( - DirectFunctionCall2( - _int_contains, - PointerGetDatum(PG_GETARG_POINTER(1)), - PointerGetDatum(PG_GETARG_POINTER(0)) - ) - )); -} - -Datum -_int_contains(PG_FUNCTION_ARGS) -{ - ArrayType *a = (ArrayType *)DatumGetPointer(PG_DETOAST_DATUM_COPY(PG_GETARG_DATUM(0))); - ArrayType *b = (ArrayType *)DatumGetPointer(PG_DETOAST_DATUM_COPY(PG_GETARG_DATUM(1))); - bool res; - - if (ARRISVOID(a) || ARRISVOID(b)) - return FALSE; - - PREPAREARR(a); - PREPAREARR(b); - res = inner_int_contains(a, b); - pfree(a); - pfree(b); - PG_RETURN_BOOL( res ); -} - -static bool -inner_int_contains(ArrayType *a, ArrayType *b) -{ - int na, - nb; - int i, - j, - n; - int *da, - *db; - - if (ARRISVOID(a) || ARRISVOID(b)) - return FALSE; - - na = ARRNELEMS(a); - nb = ARRNELEMS(b); - da = ARRPTR(a); - db = ARRPTR(b); - -#ifdef GIST_DEBUG - elog(DEBUG3, "contains %d %d", na, nb); -#endif - - i = j = n = 0; - while (i < na && j < nb) - if (da[i] < db[j]) - i++; - else if (da[i] == db[j]) - { - n++; - i++; - j++; - } - else - j++; - - return (n == nb) ? TRUE : FALSE; -} - -/***************************************************************************** - * Operator class for R-tree indexing - *****************************************************************************/ - -Datum -_int_different(PG_FUNCTION_ARGS) -{ - PG_RETURN_BOOL( ! DatumGetBool( - DirectFunctionCall2( - _int_same, - PointerGetDatum(PG_GETARG_POINTER(0)), - PointerGetDatum(PG_GETARG_POINTER(1)) - ) - )); -} - -Datum -_int_same(PG_FUNCTION_ARGS) -{ - ArrayType *a = (ArrayType *)DatumGetPointer(PG_DETOAST_DATUM_COPY(PG_GETARG_DATUM(0))); - ArrayType *b = (ArrayType *)DatumGetPointer(PG_DETOAST_DATUM_COPY(PG_GETARG_DATUM(1))); - int na, - nb; - int n; - int *da, - *db; - bool result; - bool avoid = ARRISVOID(a); - bool bvoid = ARRISVOID(b); - - if (avoid || bvoid) - return (avoid && bvoid) ? TRUE : FALSE; - - SORT(a); - SORT(b); - na = ARRNELEMS(a); - nb = ARRNELEMS(b); - da = ARRPTR(a); - db = ARRPTR(b); - - result = FALSE; - - if (na == nb) - { - result = TRUE; - for (n = 0; n < na; n++) - if (da[n] != db[n]) - { - result = FALSE; - break; - } - } - - pfree(a); - pfree(b); - - PG_RETURN_BOOL(result); -} - -/* _int_overlap -- does a overlap b? - */ -Datum -_int_overlap(PG_FUNCTION_ARGS) -{ - ArrayType *a = (ArrayType *)DatumGetPointer(PG_DETOAST_DATUM_COPY(PG_GETARG_DATUM(0))); - ArrayType *b = (ArrayType *)DatumGetPointer(PG_DETOAST_DATUM_COPY(PG_GETARG_DATUM(1))); - bool result; - - if (ARRISVOID(a) || ARRISVOID(b)) - return FALSE; - - SORT(a); - SORT(b); - - result = inner_int_overlap(a, b); - - pfree(a); - pfree(b); - - PG_RETURN_BOOL( result ); -} - -static bool -inner_int_overlap(ArrayType *a, ArrayType *b) -{ - int na, - nb; - int i, - j; - int *da, - *db; - - if (ARRISVOID(a) || ARRISVOID(b)) - return FALSE; - - na = ARRNELEMS(a); - nb = ARRNELEMS(b); - da = ARRPTR(a); - db = ARRPTR(b); - -#ifdef GIST_DEBUG - elog(DEBUG3, "g_int_overlap"); -#endif - - i = j = 0; - while (i < na && j < nb) - if (da[i] < db[j]) - i++; - else if (da[i] == db[j]) - return TRUE; - else - j++; - - return FALSE; -} - -Datum -_int_union(PG_FUNCTION_ARGS) -{ - ArrayType *a = (ArrayType *)DatumGetPointer(PG_DETOAST_DATUM_COPY(PG_GETARG_DATUM(0))); - ArrayType *b = (ArrayType *)DatumGetPointer(PG_DETOAST_DATUM_COPY(PG_GETARG_DATUM(1))); - ArrayType *result; - - if (!ARRISVOID(a)) - SORT(a); - if (!ARRISVOID(b)) - SORT(b); - - result = inner_int_union(a, b); - - if (a) - pfree(a); - if (b) - pfree(b); - - PG_RETURN_POINTER( result ); -} - -static ArrayType * -inner_int_union(ArrayType *a, ArrayType *b) -{ - ArrayType *r = NULL; - int na, - nb; - int *da, - *db, - *dr; - int i, - j; - - if (ARRISVOID(a) && ARRISVOID(b)) - return new_intArrayType(0); - if (ARRISVOID(a)) - r = copy_intArrayType(b); - if (ARRISVOID(b)) - r = copy_intArrayType(a); - - if (r) - dr = ARRPTR(r); - else - { - na = ARRNELEMS(a); - nb = ARRNELEMS(b); - da = ARRPTR(a); - db = ARRPTR(b); - - r = new_intArrayType(na + nb); - dr = ARRPTR(r); - - /* union */ - i = j = 0; - while (i < na && j < nb) - if (da[i] < db[j]) - *dr++ = da[i++]; - else - *dr++ = db[j++]; - - while (i < na) - *dr++ = da[i++]; - while (j < nb) - *dr++ = db[j++]; - - } - - if (ARRNELEMS(r) > 1) - r = _int_unique(r); - - return r; -} - - -Datum -_int_inter(PG_FUNCTION_ARGS) -{ - ArrayType *a = (ArrayType *)DatumGetPointer(PG_DETOAST_DATUM_COPY(PG_GETARG_DATUM(0))); - ArrayType *b = (ArrayType *)DatumGetPointer(PG_DETOAST_DATUM_COPY(PG_GETARG_DATUM(1))); - ArrayType *result; - - if (ARRISVOID(a) || ARRISVOID(b)) - PG_RETURN_POINTER(new_intArrayType(0)); - - SORT(a); - SORT(b); - - result = inner_int_inter(a, b); - - pfree(a); - pfree(b); - - PG_RETURN_POINTER( result ); -} - -static ArrayType * -inner_int_inter(ArrayType *a, ArrayType *b) -{ - ArrayType *r; - int na, - nb; - int *da, - *db, - *dr; - int i, - j; - - if (ARRISVOID(a) || ARRISVOID(b)) - return new_intArrayType(0); - - na = ARRNELEMS(a); - nb = ARRNELEMS(b); - da = ARRPTR(a); - db = ARRPTR(b); - r = new_intArrayType(min(na, nb)); - dr = ARRPTR(r); - - i = j = 0; - while (i < na && j < nb) - if (da[i] < db[j]) - i++; - else if (da[i] == db[j]) - { - if (i + j == 0 || (i + j > 0 && *(dr - 1) != db[j])) - *dr++ = db[j]; - i++; - j++; - } - else - j++; - - if ((dr - ARRPTR(r)) == 0) - { - pfree(r); - return new_intArrayType(0); - } - else - return resize_intArrayType(r, dr - ARRPTR(r)); -} - -static void -rt__int_size(ArrayType *a, float *size) -{ - *size = (float) ARRNELEMS(a); - - return; -} - - -/***************************************************************************** - * Miscellaneous operators and functions - *****************************************************************************/ - -/* len >= 2 */ -static bool -isort(int4 *a, int len) -{ - int4 tmp, - index; - int4 *cur, - *end; - bool r = FALSE; - - end = a + len; - do - { - index = 0; - cur = a + 1; - while (cur < end) - { - if (*(cur - 1) > *cur) - { - tmp = *(cur - 1); - *(cur - 1) = *cur; - *cur = tmp; - index = 1; - } - else if (!r && *(cur - 1) == *cur) - r = TRUE; - cur++; - } - } while (index); - return r; -} - -static ArrayType * -new_intArrayType(int num) -{ - ArrayType *r; - int nbytes = ARR_OVERHEAD(NDIM) + sizeof(int) * num; - - r = (ArrayType *) palloc(nbytes); - - MemSet(r, 0, nbytes); - r->size = nbytes; - r->ndim = NDIM; - r->flags &= ~LEAFKEY; - *((int *) ARR_DIMS(r)) = num; - *((int *) ARR_LBOUND(r)) = 1; - - return r; -} - -static ArrayType * -resize_intArrayType(ArrayType *a, int num) -{ - int nbytes = ARR_OVERHEAD(NDIM) + sizeof(int) * num; - - if (num == ARRNELEMS(a)) - return a; - - a = (ArrayType *) repalloc(a, nbytes); - - a->size = nbytes; - *((int *) ARR_DIMS(a)) = num; - return a; -} - -static ArrayType * -copy_intArrayType(ArrayType *a) -{ - ArrayType *r; - - r = new_intArrayType(ARRNELEMS(a)); - memmove(r, a, VARSIZE(a)); - return r; -} - -/* num for compressed key */ -static int -internal_size(int *a, int len) -{ - int i, - size = 0; - - for (i = 0; i < len; i += 2) - if (!i || a[i] != a[i - 1]) /* do not count repeated range */ - size += a[i + 1] - a[i] + 1; - - return size; -} - -/* r is sorted and size of r > 1 */ -static ArrayType * -_int_unique(ArrayType *r) -{ - int *tmp, - *dr, - *data; - int num = ARRNELEMS(r); - - data = tmp = dr = ARRPTR(r); - while (tmp - data < num) - if (*tmp != *dr) - *(++dr) = *tmp++; - else - tmp++; - return resize_intArrayType(r, dr + 1 - ARRPTR(r)); -} - -/********************************************************************* -** intbig functions -*********************************************************************/ -static void -gensign(BITVEC sign, int *a, int len) -{ - int i; - - /* we assume that the sign vector is previously zeroed */ - for (i = 0; i < len; i++) - { - HASH(sign, *a); - a++; - } -} - -static bool -_intbig_overlap(ArrayType *a, ArrayType *b) -{ - int i; - BITVECP da, - db; - - da = SIGPTR(a); - db = SIGPTR(b); - - LOOPBYTE(if (da[i] & db[i]) return TRUE); - return FALSE; -} - -static bool -_intbig_contains(ArrayType *a, ArrayType *b) -{ - int i; - BITVECP da, - db; - - da = SIGPTR(a); - db = SIGPTR(b); - - LOOPBYTE(if (db[i] & ~da[i]) return FALSE); - - return TRUE; -} - -static void -rt__intbig_size(ArrayType *a, float *sz) -{ - int i, - len = 0; - BITVECP bv = SIGPTR(a); - - LOOPBYTE( - len += - GETBITBYTE(bv,0) + - GETBITBYTE(bv,1) + - GETBITBYTE(bv,2) + - GETBITBYTE(bv,3) + - GETBITBYTE(bv,4) + - GETBITBYTE(bv,5) + - GETBITBYTE(bv,6) + - GETBITBYTE(bv,7) ; - bv = (BITVECP) ( ((char*)bv) + 1 ); - ); - - *sz = (float) len; - return; -} - -static ArrayType * -_intbig_union(ArrayType *a, ArrayType *b) -{ - ArrayType *r; - BITVECP da, - db, - dr; - int i; - - r = new_intArrayType(SIGLENINT); - - da = SIGPTR(a); - db = SIGPTR(b); - dr = SIGPTR(r); - - LOOPBYTE(dr[i] = da[i] | db[i]); - - return r; -} - -static ArrayType * -_intbig_inter(ArrayType *a, ArrayType *b) -{ - ArrayType *r; - BITVECP da, - db, - dr; - int i; - - r = new_intArrayType(SIGLENINT); - - da = SIGPTR(a); - db = SIGPTR(b); - dr = SIGPTR(r); - - LOOPBYTE(dr[i] = da[i] & db[i]); - - return r; -} - -Datum -g_intbig_same(PG_FUNCTION_ARGS) -{ - ArrayType *a = (ArrayType *)PG_GETARG_POINTER(0); - ArrayType *b = (ArrayType *)PG_GETARG_POINTER(1); - bool *result = (bool *)PG_GETARG_POINTER(2); - BITVECP da, - db; - int i; - - da = SIGPTR(a); - db = SIGPTR(b); - - LOOPBYTE( - if (da[i] != db[i]) - { - *result = FALSE; - PG_RETURN_POINTER( result ); - } - ); - - *result = TRUE; - PG_RETURN_POINTER( result ); -} - -Datum -g_intbig_compress(PG_FUNCTION_ARGS) -{ - GISTENTRY *entry = (GISTENTRY *)PG_GETARG_POINTER(0); - GISTENTRY *retval; - ArrayType *r, - *in; - bool maycompress = true; - int i; - - if (DatumGetPointer(entry->key) != NULL) - in = (ArrayType *) PG_DETOAST_DATUM(entry->key); - else - in = NULL; - - if (!entry->leafkey) { - LOOPBYTE( - if ( ( ((char*)ARRPTR(in))[i] & 0xff ) != 0xff ) { - maycompress = false; - break; - } - ); - if ( maycompress ) { - retval = palloc(sizeof(GISTENTRY)); - r = new_intArrayType(1); - gistentryinit(*retval, PointerGetDatum(r), - entry->rel, entry->page, entry->offset, VARSIZE(r), FALSE); - PG_RETURN_POINTER( retval ); - } - PG_RETURN_POINTER( entry ); - } - - retval = palloc(sizeof(GISTENTRY)); - r = new_intArrayType( SIGLENINT ); - - if (ARRISVOID(in)) - { - gistentryinit(*retval, PointerGetDatum(r), - entry->rel, entry->page, entry->offset, VARSIZE(r), FALSE); - if (in != (ArrayType *) DatumGetPointer(entry->key)) - pfree(in); - PG_RETURN_POINTER (retval); - } - - gensign(SIGPTR(r), - ARRPTR(in), - ARRNELEMS(in)); - - LOOPBYTE( - if( ( ((char*)ARRPTR(in))[i] & 0xff ) != 0xff ) { - maycompress = false; - break; - } - ); - - if ( maycompress ) { - pfree(r); - r = new_intArrayType(1); - } - - gistentryinit(*retval, PointerGetDatum(r), entry->rel, entry->page, entry->offset, VARSIZE(r), FALSE); - - if ( in != (ArrayType *) DatumGetPointer(entry->key)) - pfree(in); - - PG_RETURN_POINTER (retval); -} - -Datum -g_intbig_decompress(PG_FUNCTION_ARGS) -{ - GISTENTRY *entry = (GISTENTRY *)PG_GETARG_POINTER(0); - ArrayType *key; - - key = (ArrayType *) PG_DETOAST_DATUM(entry->key); - - if ( key != (ArrayType *) DatumGetPointer(entry->key)) - { - GISTENTRY *retval; - - retval = palloc(sizeof(GISTENTRY)); - - gistentryinit(*retval, PointerGetDatum(key), - entry->rel, entry->page, entry->offset, (key) ? VARSIZE(key) : 0, FALSE); - PG_RETURN_POINTER( retval ); - } - if ( ARRNELEMS(key) == 1 ) { - GISTENTRY *retval; - ArrayType *newkey; - - retval = palloc(sizeof(GISTENTRY)); - newkey = new_intArrayType(SIGLENINT); - MemSet( (void*)ARRPTR(newkey), 0xff, SIGLEN ); - - gistentryinit(*retval, PointerGetDatum(newkey), - entry->rel, entry->page, entry->offset, VARSIZE(newkey), FALSE); - PG_RETURN_POINTER( retval ); - } - PG_RETURN_POINTER( entry ); -} - -Datum -g_intbig_picksplit(PG_FUNCTION_ARGS) -{ - PG_RETURN_POINTER( _int_common_picksplit( - (bytea *)PG_GETARG_POINTER(0), - (GIST_SPLITVEC *)PG_GETARG_POINTER(1), - _intbig_union, - _intbig_inter, - rt__intbig_size, - 0.1 - ) ); -} - -Datum -g_intbig_union(PG_FUNCTION_ARGS) -{ - PG_RETURN_POINTER( _int_common_union( - (bytea *) PG_GETARG_POINTER(0), - (int *) PG_GETARG_POINTER(1), - _intbig_union - ) ); -} - -Datum -g_intbig_penalty(PG_FUNCTION_ARGS) -{ - PG_RETURN_POINTER( _int_common_penalty( - (GISTENTRY *)PG_GETARG_POINTER(0), - (GISTENTRY *)PG_GETARG_POINTER(1), - (float *) PG_GETARG_POINTER(2), - _intbig_union, rt__intbig_size - ) ); -} - -Datum -g_intbig_consistent(PG_FUNCTION_ARGS) { - GISTENTRY *entry = (GISTENTRY *)PG_GETARG_POINTER(0); - ArrayType *query = ( ArrayType * )PG_GETARG_POINTER(1); - StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2); - bool retval; - ArrayType *q; - - if ( strategy == BooleanSearchStrategy ) - PG_RETURN_BOOL(signconsistent( (QUERYTYPE*)query, - SIGPTR((ArrayType *) DatumGetPointer(entry->key)), - false ) ); - - /* XXX what about toasted input? */ - if (ARRISVOID(query)) - return FALSE; - - q = new_intArrayType(SIGLENINT); - gensign(SIGPTR(q), - ARRPTR(query), - ARRNELEMS(query)); - - switch (strategy) - { - case RTOverlapStrategyNumber: - retval = _intbig_overlap((ArrayType *) DatumGetPointer(entry->key), q); - break; - case RTSameStrategyNumber: - if ( GIST_LEAF(entry) ) - DirectFunctionCall3( - g_intbig_same, - entry->key, - PointerGetDatum(q), - PointerGetDatum(&retval) - ); - else - retval = _intbig_contains((ArrayType *) DatumGetPointer(entry->key), q); - break; - case RTContainsStrategyNumber: - retval = _intbig_contains((ArrayType *) DatumGetPointer(entry->key), q); - break; - case RTContainedByStrategyNumber: - retval = _intbig_overlap((ArrayType *) DatumGetPointer(entry->key), q); - break; - default: - retval = FALSE; - } - pfree(q); - PG_RETURN_BOOL(retval); -} - -/***************************************************************** -** Common GiST Method -*****************************************************************/ - -/* -** The GiST Union method for _intments -** returns the minimal set that encloses all the entries in entryvec -*/ -static ArrayType * -_int_common_union(bytea *entryvec, int *sizep, formarray unionf) -{ - int numranges, - i; - ArrayType *out = (ArrayType *) NULL; - ArrayType *tmp; - -#ifdef GIST_DEBUG - elog(DEBUG3, "_int_common_union in"); -#endif - - numranges = (VARSIZE(entryvec) - VARHDRSZ) / sizeof(GISTENTRY); - tmp = (ArrayType *) DatumGetPointer(((GISTENTRY *) VARDATA(entryvec))[0].key); - - for (i = 1; i < numranges; i++) - { - out = (*unionf) (tmp, (ArrayType *) - DatumGetPointer(((GISTENTRY *) VARDATA(entryvec))[i].key)); - if (i > 1 && tmp) - pfree(tmp); - tmp = out; - } - - out->flags &= ~LEAFKEY; - *sizep = VARSIZE(out); - if (*sizep == 0) - { - pfree(out); -#ifdef GIST_DEBUG - elog(DEBUG3, "_int_common_union out1"); -#endif - return NULL; - } -#ifdef GIST_DEBUG - elog(DEBUG3, "_int_common_union out"); -#endif - return (out); - -} - -/***************************************** - * The GiST Penalty method for _intments * - *****************************************/ - -static float * -_int_common_penalty(GISTENTRY *origentry, GISTENTRY *newentry, float *result, - formarray unionf, - formfloat sizef) -{ - ArrayType *ud; - float tmp1, - tmp2; - -#ifdef GIST_DEBUG - elog(DEBUG3, "penalty"); -#endif - ud = (*unionf) ((ArrayType *) DatumGetPointer(origentry->key), - (ArrayType *) DatumGetPointer(newentry->key)); - (*sizef) (ud, &tmp1); - (*sizef) ((ArrayType *) DatumGetPointer(origentry->key), &tmp2); - *result = tmp1 - tmp2; - pfree(ud); - -#ifdef GIST_DEBUG - elog(DEBUG3, "--penalty\t%g", *result); -#endif - - return (result); -} - -typedef struct { - OffsetNumber pos; - float cost; -} SPLITCOST; - -static int -comparecost( const void *a, const void *b ) { - if ( ((SPLITCOST*)a)->cost == ((SPLITCOST*)b)->cost ) - return 0; - else - return ( ((SPLITCOST*)a)->cost > ((SPLITCOST*)b)->cost ) ? 1 : -1; -} - -/* -** The GiST PickSplit method for _intments -** We use Guttman's poly time split algorithm -*/ -static GIST_SPLITVEC * -_int_common_picksplit(bytea *entryvec, - GIST_SPLITVEC *v, - formarray unionf, - formarray interf, - formfloat sizef, - float coef) -{ - OffsetNumber i, - j; - ArrayType *datum_alpha, - *datum_beta; - ArrayType *datum_l, - *datum_r; - ArrayType *union_d, - *union_dl, - *union_dr; - ArrayType *inter_d; - bool firsttime; - float size_alpha, - size_beta, - size_union, - size_inter; - float size_waste, - waste; - float size_l, - size_r; - int nbytes; - OffsetNumber seed_1 = 0, - seed_2 = 0; - OffsetNumber *left, - *right; - OffsetNumber maxoff; - SPLITCOST *costvector; - -#ifdef GIST_DEBUG - elog(DEBUG3, "--------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); - - firsttime = true; - waste = 0.0; - for (i = FirstOffsetNumber; i < maxoff; i = OffsetNumberNext(i)) - { - datum_alpha = (ArrayType *) DatumGetPointer(((GISTENTRY *) VARDATA(entryvec))[i].key); - for (j = OffsetNumberNext(i); j <= maxoff; j = OffsetNumberNext(j)) - { - datum_beta = (ArrayType *) DatumGetPointer(((GISTENTRY *) VARDATA(entryvec))[j].key); - - /* compute the wasted space by unioning these guys */ - /* size_waste = size_union - size_inter; */ - union_d = (*unionf) (datum_alpha, datum_beta); - (*sizef) (union_d, &size_union); - inter_d = (*interf) (datum_alpha, datum_beta); - (*sizef) (inter_d, &size_inter); - size_waste = size_union - size_inter; - - pfree(union_d); - - if (inter_d != (ArrayType *) NULL) - pfree(inter_d); - - /* - * are these a more promising split that what we've already - * seen? - */ - - if (size_waste > waste || firsttime) - { - waste = size_waste; - seed_1 = i; - seed_2 = j; - firsttime = false; - } - } - } - - left = v->spl_left; - v->spl_nleft = 0; - right = v->spl_right; - v->spl_nright = 0; - if ( seed_1 == 0 || seed_2 == 0 ) { - seed_1 = 1; - seed_2 = 2; - } - - datum_alpha = (ArrayType *) DatumGetPointer(((GISTENTRY *) VARDATA(entryvec))[seed_1].key); - datum_l = copy_intArrayType(datum_alpha); - (*sizef) (datum_l, &size_l); - datum_beta = (ArrayType *) DatumGetPointer(((GISTENTRY *) VARDATA(entryvec))[seed_2].key); - datum_r = copy_intArrayType(datum_beta); - (*sizef) (datum_r, &size_r); - - maxoff = OffsetNumberNext(maxoff); - /* - * sort entries - */ - costvector=(SPLITCOST*)palloc( sizeof(SPLITCOST)*maxoff ); - for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i)) { - costvector[i-1].pos = i; - datum_alpha = (ArrayType *) DatumGetPointer(((GISTENTRY *) VARDATA(entryvec))[i].key); - union_d = (*unionf)(datum_l, datum_alpha); - (*sizef)(union_d, &size_alpha); - pfree( union_d ); - union_d = (*unionf)(datum_r, datum_alpha); - (*sizef)(union_d, &size_beta); - pfree( union_d ); - costvector[i-1].cost = abs( (size_alpha - size_l) - (size_beta - size_r) ); - } - qsort( (void*)costvector, maxoff, sizeof(SPLITCOST), comparecost ); - - /* - * Now split up the regions between the two seeds. An important - * property of this split algorithm is that the split vector v has the - * indices of items to be split in order in its left and right - * vectors. We exploit this property by doing a merge in the code - * that actually splits the page. - * - * For efficiency, we also place the new index tuple in this loop. This - * is handled at the very end, when we have placed all the existing - * tuples and i == maxoff + 1. - */ - - - for (j = 0; j < maxoff; j++) { - i = costvector[j].pos; - - /* - * If we've already decided where to place this item, just put it - * on the right list. Otherwise, we need to figure out which page - * needs the least enlargement in order to store the item. - */ - - if (i == seed_1) - { - *left++ = i; - v->spl_nleft++; - continue; - } - else if (i == seed_2) - { - *right++ = i; - v->spl_nright++; - continue; - } - - /* okay, which page needs least enlargement? */ - datum_alpha = (ArrayType *) DatumGetPointer(((GISTENTRY *) VARDATA(entryvec))[i].key); - union_dl = (*unionf) (datum_l, datum_alpha); - union_dr = (*unionf) (datum_r, datum_alpha); - (*sizef) (union_dl, &size_alpha); - (*sizef) (union_dr, &size_beta); - - /* pick which page to add it to */ - 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; - size_l = size_alpha; - *left++ = i; - v->spl_nleft++; - } - else - { - if (datum_r) - pfree(datum_r); - if (union_dl) - pfree(union_dl); - datum_r = union_dr; - size_r = size_beta; - *right++ = i; - v->spl_nright++; - } - } - pfree( costvector ); - *right = *left = FirstOffsetNumber; - - datum_l->flags &= ~LEAFKEY; - datum_r->flags &= ~LEAFKEY; - v->spl_ldatum = PointerGetDatum(datum_l); - v->spl_rdatum = PointerGetDatum(datum_r); - -#ifdef GIST_DEBUG - elog(DEBUG3, "--------ENDpicksplit %d %d", v->spl_nleft, v->spl_nright); -#endif - return v; -} - -/***************************************************************************** - * BoolSearch - *****************************************************************************/ - - -#define END 0 -#define ERR 1 -#define VAL 2 -#define OPR 3 -#define OPEN 4 -#define CLOSE 5 - -/* parser's states */ -#define WAITOPERAND 1 -#define WAITENDOPERAND 2 -#define WAITOPERATOR 3 - -/* - * node of query tree, also used - * for storing polish notation in parser - */ -typedef struct NODE { - int4 type; - int4 val; - struct NODE *next; -} NODE; - -typedef struct { - char *buf; - int4 state; - int4 count; - /* reverse polish notation in list (for temprorary usage)*/ - NODE *str; - /* number in str */ - int4 num; -} WORKSTATE; - -/* - * get token from query string - */ -static int4 -gettoken( WORKSTATE* state, int4* val ) { - char nnn[16], *curnnn; - - curnnn=nnn; - while(1) { - switch(state->state) { - case WAITOPERAND: - curnnn=nnn; - if ( (*(state->buf)>='0' && *(state->buf)<='9') || - *(state->buf)=='-' ) { - state->state = WAITENDOPERAND; - *curnnn = *(state->buf); - curnnn++; - } else if ( *(state->buf) == '!' ) { - (state->buf)++; - *val = (int4)'!'; - return OPR; - } else if ( *(state->buf) == '(' ) { - state->count++; - (state->buf)++; - return OPEN; - } else if ( *(state->buf) != ' ' ) - return ERR; - break; - case WAITENDOPERAND: - if ( *(state->buf)>='0' && *(state->buf)<='9' ) { - *curnnn = *(state->buf); - curnnn++; - } else { - *curnnn = '\0'; - *val=(int4)atoi( nnn ); - state->state = WAITOPERATOR; - return ( state->count && *(state->buf) == '\0' ) - ? ERR : VAL; - } - break; - case WAITOPERATOR: - if ( *(state->buf) == '&' || *(state->buf) == '|' ) { - state->state = WAITOPERAND; - *val = (int4) *(state->buf); - (state->buf)++; - return OPR; - } else if ( *(state->buf) == ')' ) { - (state->buf)++; - state->count--; - return ( state->count <0 ) ? ERR : CLOSE; - } else if ( *(state->buf) == '\0' ) { - return ( state->count ) ? ERR : END; - } else if ( *(state->buf) != ' ' ) - return ERR; - break; - default: - return ERR; - break; - } - (state->buf)++; - } - return END; -} - -/* - * push new one in polish notation reverse view - */ -static void -pushquery( WORKSTATE *state, int4 type, int4 val ) { - NODE *tmp = (NODE*)palloc(sizeof(NODE)); - tmp->type=type; - tmp->val =val; - tmp->next = state->str; - state->str = tmp; - state->num++; -} - -#define STACKDEPTH 16 - -/* - * make polish notaion of query - */ -static int4 -makepol(WORKSTATE *state) { - int4 val,type; - int4 stack[STACKDEPTH]; - int4 lenstack=0; - - while( (type=gettoken(state, &val))!=END ) { - switch(type) { - case VAL: - pushquery(state, type, val); - while ( lenstack && (stack[ lenstack-1 ] == (int4)'&' || - stack[ lenstack-1 ] == (int4)'!') ) { - lenstack--; - pushquery(state, OPR, stack[ lenstack ]); - } - break; - case OPR: - if ( lenstack && val == (int4) '|' ) { - pushquery(state, OPR, val); - } else { - if ( lenstack == STACKDEPTH ) - elog(ERROR,"Stack too short"); - stack[ lenstack ] = val; - lenstack++; - } - break; - case OPEN: - if ( makepol( state ) == ERR ) return ERR; - if ( lenstack && (stack[ lenstack-1 ] == (int4)'&' || - stack[ lenstack-1 ] == (int4)'!') ) { - lenstack--; - pushquery(state, OPR, stack[ lenstack ]); - } - break; - case CLOSE: - while ( lenstack ) { - lenstack--; - pushquery(state, OPR, stack[ lenstack ]); - }; - return END; - break; - case ERR: - default: - elog(ERROR,"Syntax error"); - return ERR; - - } - } - - while (lenstack) { - lenstack--; - pushquery(state, OPR, stack[ lenstack ]); - }; - return END; -} - -typedef struct { - int4 *arrb; - int4 *arre; -} CHKVAL; - -/* - * is there value 'val' in array or not ? - */ -static bool -checkcondition_arr( void *checkval, int4 val ) { - int4 *StopLow = ((CHKVAL*)checkval)->arrb; - int4 *StopHigh = ((CHKVAL*)checkval)->arre; - int4 *StopMiddle; - - /* Loop invariant: StopLow <= val < StopHigh */ - - while (StopLow < StopHigh) { - StopMiddle = StopLow + (StopHigh - StopLow) / 2; - if (*StopMiddle == val) - return (true); - else if (*StopMiddle < val ) - StopLow = StopMiddle + 1; - else - StopHigh = StopMiddle; - } - return false; -} - -static bool -checkcondition_bit( void *checkval, int4 val ) { - return GETBIT( checkval, HASHVAL( val ) ); -} - -/* - * check for boolean condition - */ -static bool -execute( ITEM* curitem, void *checkval, bool calcnot, bool (*chkcond)(void *checkval, int4 val )) { - - if ( curitem->type == VAL ) { - return (*chkcond)( checkval, curitem->val ); - } else if ( curitem->val == (int4)'!' ) { - return ( calcnot ) ? - ( ( execute(curitem - 1, checkval, calcnot, chkcond) ) ? false : true ) - : true; - } else if ( curitem->val == (int4)'&' ) { - if ( execute(curitem + curitem->left, checkval, calcnot, chkcond) ) - return execute(curitem - 1, checkval, calcnot, chkcond); - else - return false; - } else { /* |-operator */ - if ( execute(curitem + curitem->left, checkval, calcnot, chkcond) ) - return true; - else - return execute(curitem - 1, checkval, calcnot, chkcond); - } - return false; -} - -/* - * signconsistent & execconsistent called by *_consistent - */ -static bool -signconsistent( QUERYTYPE *query, BITVEC sign, bool calcnot ) { - return execute( - GETQUERY(query) + query->size-1 , - (void*)sign, calcnot, - checkcondition_bit - ); -} - -static bool -execconsistent( QUERYTYPE *query, ArrayType *array, bool calcnot ) { - CHKVAL chkval; - - chkval.arrb = ARRPTR(array); - chkval.arre = chkval.arrb + ARRNELEMS(array); - return execute( - GETQUERY(query) + query->size-1 , - (void*)&chkval, calcnot, - checkcondition_arr - ); -} - -/* - * boolean operations - */ -Datum -rboolop(PG_FUNCTION_ARGS) { - return DirectFunctionCall2( - boolop, - PG_GETARG_DATUM(1), - PG_GETARG_DATUM(0) - ); -} - -Datum -boolop(PG_FUNCTION_ARGS) { - ArrayType *val = ( ArrayType * )PG_DETOAST_DATUM_COPY(PG_GETARG_POINTER(0)); - QUERYTYPE *query = ( QUERYTYPE * )PG_DETOAST_DATUM(PG_GETARG_POINTER(1)); - CHKVAL chkval; - bool result; - - if ( ARRISVOID( val ) ) { - pfree(val); - PG_FREE_IF_COPY(query,1); - PG_RETURN_BOOL( false ); - } - - PREPAREARR(val); - chkval.arrb = ARRPTR(val); - chkval.arre = chkval.arrb + ARRNELEMS(val); - result = execute( - GETQUERY(query) + query->size-1 , - &chkval, true, - checkcondition_arr - ); - pfree(val); - - PG_FREE_IF_COPY(query,1); - PG_RETURN_BOOL( result ); -} - -static void -findoprnd( ITEM *ptr, int4 *pos ) { -#ifdef BS_DEBUG - elog(DEBUG3, ( ptr[*pos].type == OPR ) ? - "%d %c" : "%d %d ", *pos, ptr[*pos].val ); -#endif - if ( ptr[*pos].type == VAL ) { - ptr[*pos].left = 0; - (*pos)--; - } else if ( ptr[*pos].val == (int4)'!' ) { - ptr[*pos].left = -1; - (*pos)--; - findoprnd( ptr, pos ); - } else { - ITEM *curitem = &ptr[*pos]; - int4 tmp = *pos; - (*pos)--; - findoprnd(ptr,pos); - curitem->left = *pos - tmp; - findoprnd(ptr,pos); - } -} - - -/* - * input - */ -Datum -bqarr_in(PG_FUNCTION_ARGS) { - char *buf=(char*)PG_GETARG_POINTER(0); - WORKSTATE state; - int4 i; - QUERYTYPE *query; - int4 commonlen; - ITEM *ptr; - NODE *tmp; - int4 pos=0; -#ifdef BS_DEBUG - char pbuf[16384],*cur; -#endif - - state.buf = buf; - state.state = WAITOPERAND; - state.count = 0; - state.num = 0; - state.str=NULL; - - /* make polish notation (postfix, but in reverse order) */ - makepol( &state ); - if (!state.num) - elog( ERROR,"Empty query"); - - commonlen = COMPUTESIZE(state.num); - query = (QUERYTYPE*) palloc( commonlen ); - query->len = commonlen; - query->size = state.num; - ptr = GETQUERY(query); - - for(i=state.num-1; i>=0; i-- ) { - ptr[i].type = state.str->type; - ptr[i].val = state.str->val; - tmp = state.str->next; - pfree( state.str ); - state.str = tmp; - } - - pos = query->size-1; - findoprnd( ptr, &pos ); -#ifdef BS_DEBUG - cur = pbuf; - *cur = '\0'; - for( i=0;i<query->size;i++ ) { - if ( ptr[i].type == OPR ) - sprintf(cur, "%c(%d) ", ptr[i].val, ptr[i].left); - else - sprintf(cur, "%d ", ptr[i].val ); - cur = strchr(cur,'\0'); - } - elog(DEBUG3,"POR: %s", pbuf); -#endif - - PG_RETURN_POINTER( query ); -} - - -/* - * out function - */ -typedef struct { - ITEM *curpol; - char *buf; - char *cur; - int4 buflen; -} INFIX; - -#define RESIZEBUF(inf,addsize) while( ( inf->cur - inf->buf ) + addsize + 1 >= inf->buflen ) { \ - int4 len = inf->cur - inf->buf; \ - inf->buflen *= 2; \ - inf->buf = (char*) repalloc( (void*)inf->buf, inf->buflen ); \ - inf->cur = inf->buf + len; \ -} - -static void -infix(INFIX *in, bool first) { - if ( in->curpol->type == VAL ) { - RESIZEBUF(in, 11); - sprintf(in->cur, "%d", in->curpol->val ); - in->cur = strchr( in->cur, '\0' ); - in->curpol--; - } else if ( in->curpol->val == (int4)'!' ) { - bool isopr = false; - RESIZEBUF(in, 1); - *(in->cur) = '!'; - in->cur++; - *(in->cur) = '\0'; - in->curpol--; - if ( in->curpol->type == OPR ) { - isopr = true; - RESIZEBUF(in, 2); - sprintf(in->cur, "( "); - in->cur = strchr( in->cur, '\0' ); - } - infix( in, isopr ); - if ( isopr ) { - RESIZEBUF(in, 2); - sprintf(in->cur, " )"); - in->cur = strchr( in->cur, '\0' ); - } - } else { - int4 op = in->curpol->val; - INFIX nrm; - - in->curpol--; - if ( op == (int4)'|' && ! first) { - RESIZEBUF(in, 2); - sprintf(in->cur, "( "); - in->cur = strchr( in->cur, '\0' ); - } - - nrm.curpol = in->curpol; - nrm.buflen = 16; - nrm.cur = nrm.buf = (char*)palloc( sizeof(char) * nrm.buflen ); - - /* get right operand */ - infix( &nrm, false ); - - /* get & print left operand */ - in->curpol = nrm.curpol; - infix( in, false ); - - /* print operator & right operand*/ - RESIZEBUF(in, 3 + (nrm.cur - nrm.buf) ); - sprintf(in->cur, " %c %s", op, nrm.buf); - in->cur = strchr( in->cur, '\0' ); - pfree( nrm.buf ); - - if ( op == (int4)'|' && ! first) { - RESIZEBUF(in, 2); - sprintf(in->cur, " )"); - in->cur = strchr( in->cur, '\0' ); - } - } -} - - -Datum -bqarr_out(PG_FUNCTION_ARGS) { - QUERYTYPE *query = (QUERYTYPE*)PG_DETOAST_DATUM(PG_GETARG_POINTER(0)); - INFIX nrm; - - if ( query->size == 0 ) - elog(ERROR,"Empty"); - nrm.curpol = GETQUERY(query) + query->size - 1; - nrm.buflen = 32; - nrm.cur = nrm.buf = (char*)palloc( sizeof(char) * nrm.buflen ); - *(nrm.cur) = '\0'; - infix( &nrm, true ); - - PG_FREE_IF_COPY(query,0); - PG_RETURN_POINTER( nrm.buf ); -} - -static int4 -countdroptree( ITEM *q, int4 pos ) { - if ( q[pos].type == VAL ) { - return 1; - } else if ( q[pos].val == (int4)'!' ) { - return 1+countdroptree(q, pos-1); - } else { - return 1 + countdroptree(q, pos-1) + countdroptree(q, pos + q[pos].left); - } -} - -/* - * common algorithm: - * result of all '!' will be = 'true', so - * we can modify query tree for clearing - */ -static int4 -shorterquery( ITEM *q, int4 len ) { - int4 index,posnot,poscor; - bool notisleft = false; - int4 drop,i; - - /* out all '!' */ - do { - index=0; - drop=0; - /* find ! */ - for(posnot=0; posnot < len; posnot++) - if ( q[posnot].type == OPR && q[posnot].val == (int4)'!') { - index=1; - break; - } - - if ( posnot == len ) - return len; - - /* last operator is ! */ - if ( posnot == len-1 ) - return 0; - - /* find operator for this operand */ - for( poscor=posnot+1; poscor<len; poscor++) { - if ( q[poscor].type == OPR ) { - if ( poscor == posnot+1 ) { - notisleft = false; - break; - } else if ( q[poscor].left + poscor == posnot ) { - notisleft = true; - break; - } - } - } - if ( q[poscor].val == (int4)'!' ) { - drop = countdroptree(q, poscor); - q[poscor-1].type=VAL; - for(i=poscor+1;i<len;i++) - if ( q[i].type == OPR && q[i].left + i <= poscor ) - q[i].left += drop - 2; - memcpy( (void*)&q[poscor-drop+1], - (void*)&q[poscor-1], - sizeof(ITEM) * ( len - (poscor-1) )); - len -= drop - 2; - } else if ( q[poscor].val == (int4)'|' ) { - drop = countdroptree(q, poscor); - q[poscor-1].type=VAL; - q[poscor].val=(int4)'!'; - q[poscor].left=-1; - for(i=poscor+1;i<len;i++) - if ( q[i].type == OPR && q[i].left + i < poscor ) - q[i].left += drop - 2; - memcpy( (void*)&q[poscor-drop+1], - (void*)&q[poscor-1], - sizeof(ITEM) * ( len - (poscor-1) )); - len -= drop - 2; - } else { /* &-operator */ - if ( - (notisleft && q[poscor-1].type == OPR && - q[poscor-1].val == (int4)'!' ) || - (!notisleft && q[poscor+q[poscor].left].type == OPR && - q[poscor+q[poscor].left].val == (int4)'!' ) - ) { /* drop subtree */ - drop = countdroptree(q, poscor); - q[poscor-1].type=VAL; - q[poscor].val=(int4)'!'; - q[poscor].left=-1; - for(i=poscor+1;i<len;i++) - if ( q[i].type == OPR && q[i].left + i < poscor ) - q[i].left += drop - 2; - memcpy( (void*)&q[poscor-drop+1], - (void*)&q[poscor-1], - sizeof(ITEM) * ( len - (poscor-1) )); - len -= drop - 2; - } else { /* drop only operator */ - int4 subtreepos = ( notisleft ) ? - poscor-1 : poscor+q[poscor].left; - int4 subtreelen = countdroptree( q, subtreepos ); - drop = countdroptree(q, poscor); - for(i=poscor+1;i<len;i++) - if ( q[i].type == OPR && q[i].left + i < poscor ) - q[i].left += drop - subtreelen; - memcpy( (void*)&q[ subtreepos+1 ], - (void*)&q[poscor+1], - sizeof(ITEM)*( len - (poscor-1) ) ); - memcpy( (void*)&q[ poscor-drop+1 ], - (void*)&q[subtreepos-subtreelen+1], - sizeof(ITEM)*( len - (drop-subtreelen) ) ); - len -= drop - subtreelen; - } - } - } while( index ); - return len; -} - - -Datum -querytree(PG_FUNCTION_ARGS) { - QUERYTYPE *query = (QUERYTYPE*)PG_DETOAST_DATUM(PG_GETARG_POINTER(0)); - INFIX nrm; - text *res; - ITEM *q; - int4 len; - - if ( query->size == 0 ) - elog(ERROR,"Empty"); - - q = (ITEM*)palloc( sizeof(ITEM) * query->size ); - memcpy( (void*)q, GETQUERY(query), sizeof(ITEM) * query->size ); - len = shorterquery( q, query->size ); - PG_FREE_IF_COPY(query,0); - - if ( len == 0 ) { - res = (text*) palloc( 1 + VARHDRSZ ); - VARATT_SIZEP(res) = 1 + VARHDRSZ; - *((char*)VARDATA(res)) = 'T'; - } else { - nrm.curpol = q + len - 1; - nrm.buflen = 32; - nrm.cur = nrm.buf = (char*)palloc( sizeof(char) * nrm.buflen ); - *(nrm.cur) = '\0'; - infix( &nrm, true ); - - res = (text*) palloc( nrm.cur-nrm.buf + VARHDRSZ ); - VARATT_SIZEP(res) = nrm.cur-nrm.buf + VARHDRSZ; - strncpy( VARDATA(res), nrm.buf, nrm.cur-nrm.buf ); - } - pfree(q); - - PG_RETURN_POINTER( res ); -} diff --git a/contrib/intarray/_int.sql.in b/contrib/intarray/_int.sql.in deleted file mode 100644 index 4d9031f6532..00000000000 --- a/contrib/intarray/_int.sql.in +++ /dev/null @@ -1,437 +0,0 @@ --- Create the user-defined type for the 1-D integer arrays (_int4) --- -BEGIN TRANSACTION; - --- Query type -CREATE FUNCTION bqarr_in(opaque) -RETURNS opaque -AS 'MODULE_PATHNAME' -LANGUAGE 'c' with (isstrict); - -CREATE FUNCTION bqarr_out(opaque) -RETURNS opaque -AS 'MODULE_PATHNAME' -LANGUAGE 'c' with (isstrict); - -CREATE TYPE query_int ( -internallength = -1, -input = bqarr_in, -output = bqarr_out -); - ---only for debug -CREATE FUNCTION querytree(query_int) -RETURNS text -AS 'MODULE_PATHNAME' -LANGUAGE 'c' with (isstrict); - - -CREATE FUNCTION boolop(_int4, query_int) RETURNS bool - AS 'MODULE_PATHNAME' LANGUAGE 'c' with (isstrict); - -COMMENT ON FUNCTION boolop(_int4, query_int) IS 'boolean operation with array'; - -CREATE FUNCTION rboolop(query_int, _int4) RETURNS bool - AS 'MODULE_PATHNAME' LANGUAGE 'c' with (isstrict); - -COMMENT ON FUNCTION rboolop(query_int, _int4) IS 'boolean operation with array'; - -CREATE OPERATOR @@ ( - LEFTARG = _int4, RIGHTARG = query_int, PROCEDURE = boolop, - COMMUTATOR = '~~', RESTRICT = contsel, JOIN = contjoinsel -); - -CREATE OPERATOR ~~ ( - LEFTARG = query_int, RIGHTARG = _int4, PROCEDURE = rboolop, - COMMUTATOR = '@@', RESTRICT = contsel, JOIN = contjoinsel -); - - --- --- External C-functions for R-tree methods --- - --- Comparison methods - -CREATE FUNCTION _int_contains(_int4, _int4) RETURNS bool - AS 'MODULE_PATHNAME' LANGUAGE 'c' with (isstrict); - -COMMENT ON FUNCTION _int_contains(_int4, _int4) IS 'contains'; - -CREATE FUNCTION _int_contained(_int4, _int4) RETURNS bool - AS 'MODULE_PATHNAME' LANGUAGE 'c' with (isstrict); - -COMMENT ON FUNCTION _int_contained(_int4, _int4) IS 'contained in'; - -CREATE FUNCTION _int_overlap(_int4, _int4) RETURNS bool - AS 'MODULE_PATHNAME' LANGUAGE 'c' with (isstrict); - -COMMENT ON FUNCTION _int_overlap(_int4, _int4) IS 'overlaps'; - -CREATE FUNCTION _int_same(_int4, _int4) RETURNS bool - AS 'MODULE_PATHNAME' LANGUAGE 'c' with (isstrict); - -COMMENT ON FUNCTION _int_same(_int4, _int4) IS 'same as'; - -CREATE FUNCTION _int_different(_int4, _int4) RETURNS bool - AS 'MODULE_PATHNAME' LANGUAGE 'c' with (isstrict); - -COMMENT ON FUNCTION _int_different(_int4, _int4) IS 'different'; - --- support routines for indexing - -CREATE FUNCTION _int_union(_int4, _int4) RETURNS _int4 - AS 'MODULE_PATHNAME' LANGUAGE 'c' with (isstrict); - -CREATE FUNCTION _int_inter(_int4, _int4) RETURNS _int4 - AS 'MODULE_PATHNAME' LANGUAGE 'c' with (isstrict); - --- --- OPERATORS --- - -CREATE OPERATOR && ( - LEFTARG = _int4, RIGHTARG = _int4, PROCEDURE = _int_overlap, - COMMUTATOR = '&&', - RESTRICT = contsel, JOIN = contjoinsel -); - ---CREATE OPERATOR = ( --- LEFTARG = _int4, RIGHTARG = _int4, PROCEDURE = _int_same, --- COMMUTATOR = '=', NEGATOR = '<>', --- RESTRICT = eqsel, JOIN = eqjoinsel, --- SORT1 = '<', SORT2 = '<' ---); - -CREATE OPERATOR <> ( - LEFTARG = _int4, RIGHTARG = _int4, PROCEDURE = _int_different, - COMMUTATOR = '<>', NEGATOR = '=', - RESTRICT = neqsel, JOIN = neqjoinsel -); - -CREATE OPERATOR @ ( - LEFTARG = _int4, RIGHTARG = _int4, PROCEDURE = _int_contains, - COMMUTATOR = '~', RESTRICT = contsel, JOIN = contjoinsel -); - -CREATE OPERATOR ~ ( - LEFTARG = _int4, RIGHTARG = _int4, PROCEDURE = _int_contained, - COMMUTATOR = '@', RESTRICT = contsel, JOIN = contjoinsel -); - - --- define the GiST support methods -CREATE FUNCTION g_int_consistent(opaque,_int4,int4) RETURNS bool - AS 'MODULE_PATHNAME' LANGUAGE 'c'; - -CREATE FUNCTION g_int_compress(opaque) RETURNS opaque - AS 'MODULE_PATHNAME' LANGUAGE 'c'; - -CREATE FUNCTION g_int_decompress(opaque) RETURNS opaque - AS 'MODULE_PATHNAME' LANGUAGE 'c'; - -CREATE FUNCTION g_int_penalty(opaque,opaque,opaque) RETURNS opaque - AS 'MODULE_PATHNAME' LANGUAGE 'c' with (isstrict); - -CREATE FUNCTION g_int_picksplit(opaque, opaque) RETURNS opaque - AS 'MODULE_PATHNAME' LANGUAGE 'c'; - -CREATE FUNCTION g_int_union(bytea, opaque) RETURNS _int4 - AS 'MODULE_PATHNAME' LANGUAGE 'c'; - -CREATE FUNCTION g_int_same(_int4, _int4, opaque) RETURNS opaque - AS 'MODULE_PATHNAME' LANGUAGE 'c'; - - --- register the default opclass for indexing -INSERT INTO pg_opclass (opcamid, opcname, opcnamespace, opcowner, opcintype, opcdefault, opckeytype) - VALUES ( - (SELECT oid FROM pg_am WHERE amname = 'gist'), - 'gist__int_ops', - (SELECT oid FROM pg_namespace WHERE nspname = 'pg_catalog'), - 1, -- UID of superuser is hardwired to 1 as of PG 7.3 - (SELECT oid FROM pg_type WHERE typname = '_int4'), - true, - 0); - - --- get the comparators for _intments and store them in a tmp table -SELECT o.oid AS opoid, o.oprname -INTO TEMP TABLE _int_ops_tmp -FROM pg_operator o, pg_type t, pg_type tq -WHERE o.oprleft = t.oid and ( o.oprright = t.oid or o.oprright=tq.oid ) - and t.typname = '_int4' - and tq.typname='query_int'; - --- make sure we have the right operators --- SELECT * from _int_ops_tmp; - --- using the tmp table, generate the amop entries - --- _int_overlap -INSERT INTO pg_amop (amopclaid, amopstrategy, amopreqcheck, amopopr) - SELECT opcl.oid, 3, false, c.opoid - FROM pg_opclass opcl, _int_ops_tmp c - WHERE - opcamid = (SELECT oid FROM pg_am WHERE amname = 'gist') - and opcname = 'gist__int_ops' - and c.oprname = '&&'; - --- _int_same -INSERT INTO pg_amop (amopclaid, amopstrategy, amopreqcheck, amopopr) - SELECT opcl.oid, 6, true, c.opoid - FROM pg_opclass opcl, _int_ops_tmp c - WHERE - opcamid = (SELECT oid FROM pg_am WHERE amname = 'gist') - and opcname = 'gist__int_ops' - and c.oprname = '='; - --- _int_contains -INSERT INTO pg_amop (amopclaid, amopstrategy, amopreqcheck, amopopr) - SELECT opcl.oid, 7, false, c.opoid - FROM pg_opclass opcl, _int_ops_tmp c - WHERE - opcamid = (SELECT oid FROM pg_am WHERE amname = 'gist') - and opcname = 'gist__int_ops' - and c.oprname = '@'; - --- _int_contained -INSERT INTO pg_amop (amopclaid, amopstrategy, amopreqcheck, amopopr) - SELECT opcl.oid, 8, false, c.opoid - FROM pg_opclass opcl, _int_ops_tmp c - WHERE - opcamid = (SELECT oid FROM pg_am WHERE amname = 'gist') - and opcname = 'gist__int_ops' - and c.oprname = '~'; - ---boolean search -INSERT INTO pg_amop (amopclaid, amopstrategy, amopreqcheck, amopopr) - SELECT opcl.oid, 20, false, c.opoid - FROM pg_opclass opcl, _int_ops_tmp c - WHERE - opcamid = (SELECT oid FROM pg_am WHERE amname = 'gist') - and opcname = 'gist__int_ops' - and c.oprname = '@@'; - -DROP TABLE _int_ops_tmp; - - --- add the entries to amproc for the support methods --- note the amprocnum numbers associated with each are specific! - -INSERT INTO pg_amproc (amopclaid, amprocnum, amproc) - SELECT opcl.oid, 1, pro.oid - FROM pg_opclass opcl, pg_proc pro - WHERE - opcamid = (SELECT oid FROM pg_am WHERE amname = 'gist') - and opcname = 'gist__int_ops' - and proname = 'g_int_consistent'; - -INSERT INTO pg_amproc (amopclaid, amprocnum, amproc) - SELECT opcl.oid, 2, pro.oid - FROM pg_opclass opcl, pg_proc pro - WHERE - opcamid = (SELECT oid FROM pg_am WHERE amname = 'gist') - and opcname = 'gist__int_ops' - and proname = 'g_int_union'; - -INSERT INTO pg_amproc (amopclaid, amprocnum, amproc) - SELECT opcl.oid, 3, pro.oid - FROM pg_opclass opcl, pg_proc pro - WHERE - opcamid = (SELECT oid FROM pg_am WHERE amname = 'gist') - and opcname = 'gist__int_ops' - and proname = 'g_int_compress'; - -INSERT INTO pg_amproc (amopclaid, amprocnum, amproc) - SELECT opcl.oid, 4, pro.oid - FROM pg_opclass opcl, pg_proc pro - WHERE - opcamid = (SELECT oid FROM pg_am WHERE amname = 'gist') - and opcname = 'gist__int_ops' - and proname = 'g_int_decompress'; - -INSERT INTO pg_amproc (amopclaid, amprocnum, amproc) - SELECT opcl.oid, 5, pro.oid - FROM pg_opclass opcl, pg_proc pro - WHERE - opcamid = (SELECT oid FROM pg_am WHERE amname = 'gist') - and opcname = 'gist__int_ops' - and proname = 'g_int_penalty'; - -INSERT INTO pg_amproc (amopclaid, amprocnum, amproc) - SELECT opcl.oid, 6, pro.oid - FROM pg_opclass opcl, pg_proc pro - WHERE - opcamid = (SELECT oid FROM pg_am WHERE amname = 'gist') - and opcname = 'gist__int_ops' - and proname = 'g_int_picksplit'; - -INSERT INTO pg_amproc (amopclaid, amprocnum, amproc) - SELECT opcl.oid, 7, pro.oid - FROM pg_opclass opcl, pg_proc pro - WHERE - opcamid = (SELECT oid FROM pg_am WHERE amname = 'gist') - and opcname = 'gist__int_ops' - and proname = 'g_int_same'; - - ---------------------------------------------- --- intbig ---------------------------------------------- --- define the GiST support methods -CREATE FUNCTION g_intbig_consistent(opaque,_int4,int4) RETURNS bool - AS 'MODULE_PATHNAME' LANGUAGE 'c'; - -CREATE FUNCTION g_intbig_compress(opaque) RETURNS opaque - AS 'MODULE_PATHNAME' LANGUAGE 'c'; - -CREATE FUNCTION g_intbig_decompress(opaque) RETURNS opaque - AS 'MODULE_PATHNAME' LANGUAGE 'c'; - -CREATE FUNCTION g_intbig_penalty(opaque,opaque,opaque) RETURNS opaque - AS 'MODULE_PATHNAME' LANGUAGE 'c' with (isstrict); - -CREATE FUNCTION g_intbig_picksplit(opaque, opaque) RETURNS opaque - AS 'MODULE_PATHNAME' LANGUAGE 'c'; - -CREATE FUNCTION g_intbig_union(bytea, opaque) RETURNS _int4 - AS 'MODULE_PATHNAME' LANGUAGE 'c'; - -CREATE FUNCTION g_intbig_same(_int4, _int4, opaque) RETURNS opaque - AS 'MODULE_PATHNAME' LANGUAGE 'c'; - --- register the opclass for indexing (not as default) -INSERT INTO pg_opclass (opcamid, opcname, opcnamespace, opcowner, opcintype, opcdefault, opckeytype) - VALUES ( - (SELECT oid FROM pg_am WHERE amname = 'gist'), - 'gist__intbig_ops', - (SELECT oid FROM pg_namespace WHERE nspname = 'pg_catalog'), - 1, -- UID of superuser is hardwired to 1 as of PG 7.3 - (SELECT oid FROM pg_type WHERE typname = '_int4'), - false, - 0); - - --- get the comparators for _intments and store them in a tmp table -SELECT o.oid AS opoid, o.oprname -INTO TEMP TABLE _int_ops_tmp -FROM pg_operator o, pg_type t, pg_type tq -WHERE o.oprleft = t.oid and ( o.oprright = t.oid or o.oprright=tq.oid ) - and t.typname = '_int4' - and tq.typname='query_int'; - --- make sure we have the right operators --- SELECT * from _int_ops_tmp; - --- using the tmp table, generate the amop entries --- note: these operators are all lossy - --- _int_overlap -INSERT INTO pg_amop (amopclaid, amopstrategy, amopreqcheck, amopopr) - SELECT opcl.oid, 3, true, c.opoid - FROM pg_opclass opcl, _int_ops_tmp c - WHERE - opcamid = (SELECT oid FROM pg_am WHERE amname = 'gist') - and opcname = 'gist__intbig_ops' - and c.oprname = '&&'; - --- _int_contains -INSERT INTO pg_amop (amopclaid, amopstrategy, amopreqcheck, amopopr) - SELECT opcl.oid, 7, true, c.opoid - FROM pg_opclass opcl, _int_ops_tmp c - WHERE - opcamid = (SELECT oid FROM pg_am WHERE amname = 'gist') - and opcname = 'gist__intbig_ops' - and c.oprname = '@'; - --- _int_contained -INSERT INTO pg_amop (amopclaid, amopstrategy, amopreqcheck, amopopr) - SELECT opcl.oid, 8, true, c.opoid - FROM pg_opclass opcl, _int_ops_tmp c - WHERE - opcamid = (SELECT oid FROM pg_am WHERE amname = 'gist') - and opcname = 'gist__intbig_ops' - and c.oprname = '~'; - --- _int_same -INSERT INTO pg_amop (amopclaid, amopstrategy, amopreqcheck, amopopr) - SELECT opcl.oid, 6, true, c.opoid - FROM pg_opclass opcl, _int_ops_tmp c - WHERE - opcamid = (SELECT oid FROM pg_am WHERE amname = 'gist') - and opcname = 'gist__intbig_ops' - and c.oprname = '='; - ---boolean search -INSERT INTO pg_amop (amopclaid, amopstrategy, amopreqcheck, amopopr) - SELECT opcl.oid, 20, true, c.opoid - FROM pg_opclass opcl, _int_ops_tmp c - WHERE - opcamid = (SELECT oid FROM pg_am WHERE amname = 'gist') - and opcname = 'gist__intbig_ops' - and c.oprname = '@@'; - -DROP TABLE _int_ops_tmp; - - --- add the entries to amproc for the support methods --- note the amprocnum numbers associated with each are specific! - -INSERT INTO pg_amproc (amopclaid, amprocnum, amproc) - SELECT opcl.oid, 1, pro.oid - FROM pg_opclass opcl, pg_proc pro - WHERE - opcamid = (SELECT oid FROM pg_am WHERE amname = 'gist') - and opcname = 'gist__intbig_ops' - and proname = 'g_intbig_consistent'; - -INSERT INTO pg_amproc (amopclaid, amprocnum, amproc) - SELECT opcl.oid, 2, pro.oid - FROM pg_opclass opcl, pg_proc pro - WHERE - opcamid = (SELECT oid FROM pg_am WHERE amname = 'gist') - and opcname = 'gist__intbig_ops' - and proname = 'g_intbig_union'; - -INSERT INTO pg_amproc (amopclaid, amprocnum, amproc) - SELECT opcl.oid, 3, pro.oid - FROM pg_opclass opcl, pg_proc pro - WHERE - opcamid = (SELECT oid FROM pg_am WHERE amname = 'gist') - and opcname = 'gist__intbig_ops' - and proname = 'g_intbig_compress'; - -INSERT INTO pg_amproc (amopclaid, amprocnum, amproc) - SELECT opcl.oid, 4, pro.oid - FROM pg_opclass opcl, pg_proc pro - WHERE - opcamid = (SELECT oid FROM pg_am WHERE amname = 'gist') - and opcname = 'gist__intbig_ops' - and proname = 'g_intbig_decompress'; - -INSERT INTO pg_amproc (amopclaid, amprocnum, amproc) - SELECT opcl.oid, 5, pro.oid - FROM pg_opclass opcl, pg_proc pro - WHERE - opcamid = (SELECT oid FROM pg_am WHERE amname = 'gist') - and opcname = 'gist__intbig_ops' - and proname = 'g_intbig_penalty'; - -INSERT INTO pg_amproc (amopclaid, amprocnum, amproc) - SELECT opcl.oid, 6, pro.oid - FROM pg_opclass opcl, pg_proc pro - WHERE - opcamid = (SELECT oid FROM pg_am WHERE amname = 'gist') - and opcname = 'gist__intbig_ops' - and proname = 'g_intbig_picksplit'; - -INSERT INTO pg_amproc (amopclaid, amprocnum, amproc) - SELECT opcl.oid, 7, pro.oid - FROM pg_opclass opcl, pg_proc pro - WHERE - opcamid = (SELECT oid FROM pg_am WHERE amname = 'gist') - and opcname = 'gist__intbig_ops' - and proname = 'g_intbig_same'; - -END TRANSACTION; diff --git a/contrib/intarray/bench/bench.pl b/contrib/intarray/bench/bench.pl deleted file mode 100755 index 2e30956721c..00000000000 --- a/contrib/intarray/bench/bench.pl +++ /dev/null @@ -1,104 +0,0 @@ -#!/usr/bin/perl - -use strict; -# make sure we are in a sane environment. -use DBI(); -use DBD::Pg(); -use Time::HiRes qw( usleep ualarm gettimeofday tv_interval ); -use Getopt::Std; - -my %opt; -getopts('d:b:s:veorauc', \%opt); - -if ( !( scalar %opt && defined $opt{s} ) ) { - print <<EOT; -Usage: -$0 -d DATABASE -s SECTIONS [-b NUMBER] [-v] [-e] [-o] [-r] [-a] [-u] --d DATABASE -DATABASE --b NUMBER -number of repeats --s SECTIONS -sections, format sid1[,sid2[,sid3[...]]]] --v -verbose (show SQL) --e -show explain --r -use RD-tree index --a -AND section --o -show output --u -unique --c -count - -EOT - exit; -} - -$opt{d} ||= '_int4'; -my $dbi=DBI->connect('DBI:Pg:dbname='.$opt{d}); - -my %table; -my @where; - -$table{message}=1; - -if ( $opt{a} ) { - if ( $opt{r} ) { - push @where, "message.sections @ '{$opt{s}}'"; - } else { - foreach my $sid ( split(/[,\s]+/, $opt{s} )) { - push @where, "EXISTS ( select message_section_map.mid from message_section_map where message.mid=message_section_map.mid and message_section_map.sid = $sid )"; - } - } -} else { - if ( $opt{r} ) { - push @where, "message.sections && '{$opt{s}}'"; - } else { - $table{message_section_map} = 1; - push @where, "message.mid = message_section_map.mid"; - push @where, "message_section_map.sid in ($opt{s})"; - } -} - -my $outf; -if ( $opt{c} ) { - $outf = ( $opt{u} ) ? 'count( distinct message.mid )' : 'count( message.mid )'; -} else { - $outf = ( $opt{u} ) ? 'distinct( message.mid )' : 'message.mid'; -} -my $sql = "select $outf from ".join(', ', keys %table)." where ".join(' AND ', @where).';'; - -if ( $opt{v} ) { - print "$sql\n"; -} - -if ( $opt{e} ) { - $dbi->do("explain $sql"); -} - -my $t0 = [gettimeofday]; -my $count=0; -my $b=$opt{b}; -$b||=1; -my @a; -foreach ( 1..$b ) { - @a=exec_sql($dbi,$sql); - $count=$#a; -} -my $elapsed = tv_interval ( $t0, [gettimeofday]); -if ( $opt{o} ) { - foreach ( @a ) { - print "$_->{mid}\t$_->{sections}\n"; - } -} -print sprintf("total: %.02f sec; number: %d; for one: %.03f sec; found %d docs\n", $elapsed, $b, $elapsed/$b, $count+1 ); -$dbi -> disconnect; - -sub exec_sql { - my ($dbi, $sql, @keys) = @_; - my $sth=$dbi->prepare($sql) || die; - $sth->execute( @keys ) || die; - my $r; - my @row; - while ( defined ( $r=$sth->fetchrow_hashref ) ) { - push @row, $r; - } - $sth->finish; - return @row; -} - diff --git a/contrib/intarray/bench/create_test.pl b/contrib/intarray/bench/create_test.pl deleted file mode 100755 index b39d1fb473c..00000000000 --- a/contrib/intarray/bench/create_test.pl +++ /dev/null @@ -1,73 +0,0 @@ -#!/usr/bin/perl - -use strict; -print <<EOT; -create table message ( - mid int not null, - sections int[] -); -create table message_section_map ( - mid int not null, - sid int not null -); - -EOT - -open(MSG,">message.tmp") || die; -open(MAP,">message_section_map.tmp") || die; - -srand( 1 ); -#foreach my $i ( 1..1778 ) { -#foreach my $i ( 1..3443 ) { -#foreach my $i ( 1..5000 ) { -#foreach my $i ( 1..29362 ) { -#foreach my $i ( 1..33331 ) { -#foreach my $i ( 1..83268 ) { -foreach my $i ( 1..200000 ) { - my @sect; - if ( rand() < 0.7 ) { - $sect[0] = int( (rand()**4)*100 ); - } else { - my %hash; - @sect = grep { $hash{$_}++; $hash{$_} <= 1 } map { int( (rand()**4)*100) } 0..( int(rand()*5) ); - } - if ( $#sect < 0 || rand() < 0.1 ) { - print MSG "$i\t\\N\n"; - } else { - print MSG "$i\t{".join(',',@sect)."}\n"; - map { print MAP "$i\t$_\n" } @sect; - } -} -close MAP; -close MSG; - -copytable('message'); -copytable('message_section_map'); - -print <<EOT; - -CREATE unique index message_key on message ( mid ); ---CREATE unique index message_section_map_key1 on message_section_map ( mid, sid ); -CREATE unique index message_section_map_key2 on message_section_map ( sid, mid ); -CREATE INDEX message_rdtree_idx on message using gist ( sections gist__int_ops ); -VACUUM ANALYZE; - -select count(*) from message; -select count(*) from message_section_map; - - - -EOT - - -unlink 'message.tmp', 'message_section_map.tmp'; - -sub copytable { - my $t = shift; - - print "COPY $t from stdin;\n"; - open( FFF, "$t.tmp") || die; - while(<FFF>) { print; } - close FFF; - print "\\.\n"; -} diff --git a/contrib/intarray/data/test__int.data b/contrib/intarray/data/test__int.data deleted file mode 100644 index b3903d0f33a..00000000000 --- a/contrib/intarray/data/test__int.data +++ /dev/null @@ -1,7000 +0,0 @@ -{18,31,54,95} -{23,50,13,9,39} -{99,54,77} -{79,83,16,63,32} -{52,41,61,79,94,87} -{76,59,39,36,21} -{} -{41,79,76,96,3} -{25,59,5,96,32} -{92,58,12,57} -{24,48,41,88} -{39,5,17} -{10,41,78,25,35} -{31,89,4} -{68,74,94} -{97,78,44,68,81,16} -{87,76} -{30,81} -{72,20,99,26} -{87,90,98,40,44} -{24,99,66,61} -{79,8,48,16} -{62,99,48,80,75,39} -{10,60,35,15} -{45,71,10,97,56} -{64,79,19,31} -{30,57,42,31,45} -{61,42,14,26} -{12,38,65,36,56,36} -{17,62,18,56} -{84,85,90,60,55,17} -{27,11,82,20,43} -{14,27,18,48,39,51} -{53,13,52} -{56,35,81,60,27} -{79,89,89,7} -{65,17,31,17,29,85} -{21,3} -{53,55,16,83,4} -{62,3,63} -{73,40,99} -{23,80} -{2,74,42,37,21} -{12,16} -{80,60} -{19,62,34} -{38,19,31,6,15,2} -{63,96,64,4,36,15} -{9,3} -{91,87,15,18,7,66} -{17,10} -{77,96} -{11,43,31,2,89} -{17,77,89,50} -{24,6,61,88,51} -{61,50,59,90,5,89} -{58,1,39,48} -{78,36,70,92} -{43,3,22,95,51} -{} -{88,64,25,64,86} -{34,6,49,90,25} -{86,35,13,22} -{21,44,83} -{42,88,72,65,59,96} -{36,33,1,98} -{16,54} -{35,16,44} -{73,23,20} -{84,25,1,52,35} -{27,36,54,87,31} -{38,47,83,3} -{64,13} -{65,84,85,16,22} -{57,9,39,73} -{89,11,67,55,73} -{78,39,84,63,62,45} -{50,63,8} -{} -{96,36,58,65,96} -{59,86,41,30} -{90,60,39,47,19} -{70,100,73,99} -{} -{85,14,39} -{76,53} -{96,38,52,13,87,85} -{97,51,15,30,53,87} -{30,59,9,40,13} -{31,91,68,79} -{37,56,39,78,75} -{82,2,47} -{33,25,45,40} -{51,21,92,20,18,76} -{84,93,36,95,34,69} -{66,25,5,40} -{77,6,57,42} -{} -{88,81,85,37,12} -{56,73,38} -{70,70,6,19} -{82,54,91} -{75,8} -{45,33,64,90,95} -{8,71,66,12} -{56,26,68,94} -{70,77,4,96,62,83} -{23,87} -{34,34,4,33} -{28,84} -{78,75,77} -{88,53} -{27,38} -{2,2,82} -{30,52,88,61,33} -{29,72,94,68} -{85,72} -{88,4} -{63,90,43,66,24,33} -{88,48,47} -{3,11,98,37,61} -{45,65,63,15,38} -{79,45,56,94} -{56,74,78,19,76} -{24,81,64,13,100} -{93,27,63,71,27,3} -{74,13,85,86,32,60} -{98,40,63,13} -{41,95,19,93,17,84} -{90,28,100,100,19,2} -{35,15,54} -{29,81,77} -{54,64,63,12,18} -{38,43,85,21,35} -{84,28,27,4,80,27} -{80,77,55,98} -{13,71,48,55,89,38} -{58,43,27,5,57} -{5,33,96,6} -{73,93,87,69,100,24} -{58,96,38,85,55,51} -{37,30,88,4,8,59} -{24,68,43,48,18,84} -{23,100,82,30,42} -{23,36,16,99,27} -{41,75} -{66,41,10,37,16,6} -{54,49,60} -{4,56,44,72,40} -{71,96,67,100,59} -{7,41} -{8,3,27} -{38,69,47,68,5,24} -{43,100,59,62} -{92,14,34,5,71,48} -{72,5,91,29,99,36} -{62,71,37,80,62,50} -{32,45,17} -{89,68} -{52,17,55} -{21,47,15,92} -{36,100,5} -{14,76,59,11,15} -{59,72} -{37,55,89,49} -{87,79,96,20,93} -{6,44} -{32,46,25} -{27,47,76,4,54} -{2,16} -{90,36} -{11,19,27,79} -{54,4} -{72,88} -{14,85,71,69,5,22} -{31,48} -{28,35,18} -{77,55,100,73,57,62} -{} -{14,59,53} -{98,3} -{13,56} -{26,61,88,54,88,33} -{70,12} -{55,16,15,42,76} -{13,75} -{97,38,82,51,86,53} -{41,76,39,84,32} -{94,66,47} -{55,28} -{} -{94,65,59,20} -{55,50,56,14,58} -{14,94,52,25,69,95} -{20,96} -{37,38} -{26,35,9,98,74} -{11,9,41,79} -{36,57,87,69,92,89} -{11,39,60,4,47,3} -{97,5} -{16,58,38,98,42} -{46,69} -{35,54} -{36,79,54} -{} -{63,78} -{12,86,52,29,60,30} -{29,27,58,86,42,62} -{42,12,60} -{90,93,85,29} -{16,8,45} -{29,33,85} -{32,14,6,47,74} -{14,85,14,26,3} -{46,71,10,16} -{30,63} -{} -{91,30,56} -{46,36,68,91,36,88} -{24,61} -{66,21,80,14} -{43,63,50,21,11} -{38,46,18,51} -{38,28,70} -{17,41,76,1,30} -{47,63} -{56,80,85,1,7,97} -{75,5,79,32} -{5,17,66,51,68} -{6,83,2} -{25,40,79,84} -{58,38,12,68} -{55,86,20,67,27} -{58,64} -{14,51} -{12,86,57,68} -{61,91,65,3,83,68} -{40,31,82,21} -\N -{24,64,35,32} -{32,83,18,27,43,32} -{50,83} -{94,84,58,3,25,79} -{66,2,27,36,24} -{71,34} -{17,57} -{22,40,49,50,10} -{79,62,94,78} -{92,79,24,72} -{23,41} -{69,60,77,70,18,48} -{39,45,91,85} -{27,43,22,21,85} -{84,51,96,7,18} -{100,38,69,93,66,39} -{73,42,35,15,69,98} -{100,17,37,15,40} -{1,91,2,17,90,48} -{18,12,52,24} -{39,43,89} -{16,13,88} -{69,8,75} -{34,91,54,81} -{37,68,89,1,56} -{81,83,39,36,14} -{12,15,2} -{14,16,88,43} -{59,12} -{1,62,21,94} -{29,43,70,52,93} -{29,36,56,78} -{91,56,86,89,53} -{14,83,39,94} -{29,58,72,4,45} -{76,56,84,28,58} -{4,52,6,88,43,17} -{21,1,35,62,77,6} -{78,74} -{1,20,93,43} -\N -{30,100,35,94,74,64} -{81,3,21,4} -{9,19,33} -{28,62,40,64,26} -{69,72,26,30,90} -{52,70,78,43} -{91,58,33,22,92,26} -{98,36,96,94,66} -{86,43,82} -{93,52,4,58,51} -\N -{49,61,80,79,90} -{50,81,72} -{57,29} -{54,31,36} -{52,31,6,48,2} -{4,51,37,83,17} -{60,20,94,82,18} -{52,64,26,81,69,61} -{39,8,22,2,8} -{31,25,95,99} -{11,72,30,95,20,28} -{78,87} -{21,40,98,41,73,33} -{67,88,42,62,11,47} -{85,1} -{4,68,100,72,24} -{82,43} -{97,55,47,52} -{51,52} -{20,21} -{69,46,34,59,54,61} -{9,31,43} -{68,20} -{73,63} -{71,12,93,8,48,10} -{44,46,42,91,21} -{98,52} -{45,60} -{95,38,30,3} -{27,77,2,46,53,18} -{99,5} -{79,33,34,48,82} -{3,29,82,72,35} -{73,75,83} -{25,43,37,26} -\N -{51,95,40} -{18,23,10,90,15,20} -{85,66} -{25,76,22,87,88,18} -{92,4} -{27,51} -{25,77,12,37} -{44,52,69,39,21,63} -{94,30,74,36} -{60,18} -{62,88,94,93,26} -{5,72,96,25} -{99,1,85,98,85,70} -{33,21,37,19} -{44,78} -{47,2,73,32,3} -{91,35,10,81} -{80,64,7,45,84} -{86,16,96,8,88} -{32,29,84,81,30,8} -{51,28,6,16} -{88,51,50,54,56,96} -{79,19,41,40} -{40,26,10,26,2} -{60,34,3,29} -{68,80,70,56} -{60,23,39} -{50,69,6,71,70,25} -{98,53,94,14,45,11} -{98,39,64,89,98,32} -\N -{45,5,15,23,41,63} -{54,31,55,58,32} -{36,56} -{38,78,65,4,75,38} -\N -{40,6,93,40,13,59} -{42,50,10,65,96} -{6,94,49} -{63,44,36,55} -{40,79} -{39,75,27} -{8,31} -{81,75} -{99,82,85,34,24,89} -{86,82,20} -{63,96} -{47,83,29} -{70,46,48} -{44,11} -{94,19,84,79,77,22} -{68,47,100,48,65,77} -\N -{76,12,86,58} -{13,14,79,61,12} -{68,65,16,93,89} -{95,18,29,89,92,43} -{19,12,50,47} -{82,93,85} -{71,40,85} -{95,96,100,86} -{2,40,71,36,25} -{11,95,25} -{79,46,41,35,39} -\N -\N -{88,29} -{54,14,94,88} -{59,67,81,41} -{46,68,78,56,47,30} -{5,76,87} -{23,89,47,46} -{47,98,14,31,1,60} -{32,14,96,61,37} -{79,66,93} -{98,1,77,44} -{21,68,2,31,17} -{94,23,15} -{48,47,57,94,49,71} -{54,3} -{99,40,81,86,81} -{85,12,98,81,5} -{60,41,21} -{38,82,55,41,96} -{11,98,12,69,93} -{11,70,66,44} -{23,92,80} -{10,8,43,97} -{17,30} -{78,56,58} -{84,87,84} -{12,32,7,58,47,48} -{29,46} -{87,34} -{59,30,72,85,71} -{67,48,83,98} -{35,10,73,71,1,77} -{21,51,16,60,64,12} -{36,61} -{54,98} -{44,74,84} -{83,14} -{71,52,48,48,15,92} -{79,78,98,35} -{52,29,47,86,96} -{10,37} -{21,25} -{57,22,28,30,97,47} -{15,28} -{88,24,98,45,65} -{78,42} -{36,70} -{40,48} -{72,3,78,69,57,33} -\N -{21,96,16,21,75,23} -{55,5,72,45} -{99,2,72,29} -{48,17} -{84,84,40,1,59} -{34,11} -{34,80,45,31} -{56,82,25,65,22,64} -{10,4,55} -{74,67,42,74,80} -{84,22,42,6,87,30} -{6,51,89,2,84,78} -{19,95,93,87,8} -{45,84,25} -{7,12,16,92} -{89,82,16} -{22,64} -{16,31,49,48,45,14} -{69,64,19,14,39,8} -{40,96,26,48,65} -{17,45,4,57} -{73,8} -{85,89,1,15,74,51} -\N -{57,89} -{25,12,55} -{39,62,35} -{85,88,71,98,83} -{64,63,75,72} -{100,40,38,1} -{2,44} -{13,46,59,43} -{87,9,93,50} -{77,7,11,30} -{61,11,18} -{19,25,68,83} -{67,25} -{54,18,85} -{96,81,38,11,3} -{87,32,47,79,62,56} -{42,49} -{41,65,24,13,79,75} -{85,32,96} -\N -{3,63,47,84,67,13} -{53,57,59,61} -{95,27,8,89,35} -{76,78,76,76,14,37} -{31,62,65} -{97,57,60,80} -{18,81,93,67} -{8,10} -{65,25} -{68,1,62,63,64,88} -{27,56,74} -{29,61,78,40} -{54,72} -{96,30,71,21,99} -{67,11,67} -{26,65,31} -{89,90,89,68} -{56,39,63,39} -{50,67} -{72,100,24,84,9} -{29,57,65,37,3} -{72,75,79,30} -{78,44,87,67} -{100,19} -{35,60,82} -{16,83,69,38} -{29,98,13,60} -{42,60,87} -{18,67,60} -{31,77,50} -{3,22,40,59,7} -{82,80} -\N -{32,92,70,30,18,35} -{48,38,92,82} -{10,92,66,59} -{4,67,42,21,71} -{27,88,20,21,9} -{46,22,27,85,36} -{42,55,36} -{24,2,96} -{96,48,40,48,52} -{15,5,90,10,68,20} -{30,2,67,92,96,63} -{16,82,87,26} -{88,98,76,29} -{29,11,94,23} -{58,20} -{52,18,55,73} -{20,81,52,19,37} -{93,21,97} -{2,77} -{46,91,80,48,71,20} -{87,7,93} -{68,77,61} -{59,33,52} -{67,62,89,2,62,90} -{30,82,72,44} -{72,18,60,38} -{11,14,59} -{74,65,54,58,67,66} -{74,56,40,73,50,66} -{42,17,56,59,53,19} -{75,25,76,9,72,50} -{14,57} -{61,47} -{90,11,72,13} -{52,27} -{80,84,53,55,98} -{16,26,55,17,79,96} -{42,73,77} -{6,84,67,54,96} -{99,48,99,63,73,77} -{5,41,72,5,88,81} -{19,20,20} -{21,89,55,44} -{82,67,11,64,61,5} -{44,34,8,62,53} -{75,53,66,36,100} -{46,65,6,70,4} -{84,10,56,35,18} -{65,60} -{88,56,27,11} -{10,9,97} -{97,49,100,100,76,32} -{2,98,57} -{47,57,84,74,79} -{80,9,24} -{96,33,86,28,19} -{43,76} -{46,14,55,92} -{60,69,66,62,22} -{45,85} -{45,9,36,13,45,1} -{24,49,8,37,66,64} -{98,53,96,47,2} -{36,44,32,4} -{77,36,78,51,63} -{82,36} -\N -{54,55,33,45,69,18} -{82,93} -{65,59,2,62,10,25} -{75,70,76,69,7,23} -{10,34,67,85} -{94,66,28,40,64,41} -{35,73,64,28,45,68} -{75,2} -{58,49,4,87,19} -{91,99,11,66,75,70} -{26,64} -\N -{13,51,18} -{39,33,21,18} -{27,50,82,2,3,71} -{51,89,44,53} -{88,91,34} -{45,96,27,12,51,52} -{31,96} -{2,9,54,89} -\N -{57,99} -{87,84,70,7,98,42} -{32,80} -{57,64,28} -{24,39,76,4,30} -{59,38,15,45,47,28} -{71,20,37,1} -{72,59} -{7,44} -{50,37,18,1,58,40} -{13,18,21,56} -{72,3,26,74,91} -{60,22,71,49} -{55,82,61,8,48,66} -{28,22,75,41,52} -{51,63,27,41,16} -{59,89,40,85,86} -{12,1} -{52,11,6} -{37,10,43,88,15,7} -{14,94,81} -{34,56,57,4} -{81,43,11,88,74,76} -\N -{67,10,50,79,70,35} -{14,51} -{49,50,23,84} -{51,41,57,100,19,14} -{31,55,40,96} -{8,42,33} -{83,34,1} -{56,80,22,93} -\N -{8,77,91} -{58,39} -{55,30,74} -{50,22,63,73} -{80,19,67,70,18} -{7,99,45,23,59,78} -{36,97,10,33,22,45} -{43,78,90} -\N -{1,68} -{63,95,54} -{5,67,61,37,89} -{32,97,2,56} -{83,31,6,80,63} -\N -{34,15,30,40,16} -{13,43,6} -{35,86,31} -{45,59,4,95,26} -{63,48,25} -{56,97,89,45,87,21} -{42,81,69} -{49,99,87} -{81,21,15,36,70,2} -{93,41,53} -{54,71,82} -{88,90,51} -{100,35,18} -{88,81} -{76,16,87,14} -{16,83,81,44} -{16,53,100,91} -{55,75,92} -{27,97,76,88,66} -{14,100,95,95} -{95,84,93,29,67} -{32,10} -{82,12,51} -{40,6,18,14,29,70} -{3,100,81} -{83,69} -{35,63,31,15} -{5,100,81,54,37,78} -{99,76,33} -{88,85,16} -{46,20,15,10,6,90} -{53,15,75,76,94} -{5,76} -{16,7,21,70} -{3,84,15} -{29,58,73,91} -{82,39,64} -{49,66,83,76} -{79,49,19,67,18,76} -{9,56,41} -{12,22,19} -{62,54} -{20,73,40} -{34,53,58,68,96} -{97,14,61,63} -{38,55,90,63} -{83,78,81,29,12,46} -{96,97,40,89,10} -{67,33,19,19,74,47} -{78,31} -{92,74,93} -{59,54,90,52,29,87} -{92,39,55,89,81,21} -{20,85,64} -{13,97} -{88,18,85,24,54,90} -{67,51,47} -{27,29,90} -{48,27,7,92} -{100,37,24,41,68,66} -{45,7,100,83,51} -{34,10} -{60,36,44} -{55,46,4} -{86,64} -{61,77,98,64} -{14,82,14,50,1} -\N -{53,31} -{64,43,35,44,98,75} -{98,15,52,58,76} -{55,94,92,40,80} -{1,14,100,42,45,74} -{13,90,84,97,18,92} -\N -{13,91} -{67,33,15} -{18,96,38} -{95,70,34,100} -{17,29,64,32} -{19,14,83,69,60,99} -{69,29,64,61,45,17} -{78,48,24} -{40,60,61,93,17} -{19,89,22,71} -{48,8,13,11,56} -{75,18,77,100} -{29,78} -{51,92,97,31} -{83,5,2,97,68,69} -{39,86,86,94,41} -{66,21,27} -{30,84,11,60} -{50,61,28,46,38,45} -{12,59,66,80,15,64} -{69,22} -{30,54,58,99} -{14,28,80,22} -{44,31,14,61,83,72} -{55,53,78,91,76,55} -{43,3,90,22,7} -{51,34,24} -{3,99,5,72,82} -{95,38,61} -{22,8} -{78,40,93,65,18,26} -{21,17,19,8,89} -\N -\N -{94,88,27} -{49,45} -{67,24,64,86,18,1} -{5,33,18,84,51} -{15,71,89,48,94,81} -{71,69} -{98,63,73,64} -{14,75,12} -{47,42,88,13} -{35,51,60} -{63,41} -{73,11,66,99,8} -\N -{2,17,6,44,97} -{95,24} -{2,13,35,21} -{76,29} -{81,37,21} -{23,63,27,53} -{70,66,58,27,4} -{69,62,22} -{62,96,44} -{68,87,99} -{51,40,81,52,93} -{81,11,45,92,22,21} -{5,39,46} -{44,7} -{14,63,62,9,12} -{9,19,90,72,51} -{70,61,24,36} -\N -{29,19,3,30} -{76,86,28,58,38} -{59,27} -{9,65,65,10,37,6} -{89,51,50,23} -{65,2} -{33,51} -{25,55,69,55,1,78} -{76,71,93,46,23} -{70,30,50,11,2,89} -{74,39} -{4,29,22,80,15,23} -{16,30,69,76,61,67} -{43,34,4,70,36} -{59,32,25,93,32,98} -{64,4} -{52,33,47} -{31,49,7,62,7,95} -{44,69,12,45,34,8} -{81,37,83,35,3} -{24,74,16,89,94,27} -{79,71,72,49,88,35} -{17,96,72,87,48} -{81,18,50} -{11,19,70} -{42,95,42,58,90} -{27,65,83,86,33} -{55,7} -{43,55,92,79} -{97,55} -{85,25} -{93,42,69,44,26,78} -{2,40,46,19,84} -{8,42,16,26,87} -{36,8,42} -{31,47,61,44,13} -{85,97,47} -{27,30,71,88,15,100} -{69,27,4,19} -{3,52,31,62,98} -{64,86} -{91,6} -{76,40} -{57,77,7,40} -{71,34,48,53,37} -{36,72} -{61,99,53,2,31,6} -{86,15} -{52,93,59,51} -{57,27,52} -{48,67,31,69} -{34,90,37,73,60,83} -{71,24,49,59} -{93,71,90} -{77,31,77} -{47,40,32,20} -{97,40,63,80,44} -{88,55,10,40} -{86,36,40,72,38,9} -{31,97} -{56,19,55,62,60} -{53,95} -{33,36} -{50,12,55,42,96,100} -{41,17,100,76} -{65,1,61,69,64,21} -{90,92} -\N -{74,42,86} -{2,4} -{99,78,5,92,1,61} -{1,69} -{80,73,60,31} -\N -{10,25,13} -{50,34,75} -{12,90,6,36,42} -{23,54,46} -{67,28,66,87} -{8,88,88,51,55,32} -{15,19,24,91,75} -{80,16,70} -{41,7,90,37} -{97,57,32,21} -{54,74,29,12,55,78} -{60,76,37,92,44,73} -{1,56,14} -{40,79} -{97,1,30,78,56} -{36,25,61} -{33,3,51,30,38} -{2,94,19,15} -{7,38,72} -{96,18,3} -{18,95,15,62,74,53} -{59,61} -{18,66,66,65,4,33} -{49,83,10} -{17,52,90,39,61,87} -{38,92,55,26} -{8,43} -{77,51,68,23,47} -{27,65,24,43,88,73} -{54,34,30,2,19,62} -{12,36,81,24,66,8} -{38,91,90,99,84} -{51,55,94,97,91,15} -{50,42,20,22} -{70,4,22} -{64,26} -{56,86,16,21,31,61} -{7,19,86,49,10,53} -{81,16,74} -{95,9,11,46,47} -{34,23,16} -{94,38,19,4,4} -{39,79} -{41,3,62} -{84,67,53,90,46} -{17,46,23} -{62,1,5,58,52,1} -{23,83,80,62,19} -{99,61,77} -{51,95,48,96,75} -{39,2,6,95,43,36} -{69,9,59} -{62,97,31} -{75,96} -{33,29,35,13,94,78} -{28,71,16,99} -{72,86,25} -{5,28,15,33} -\N -{13,13,52,20} -{58,98,83,85,81} -{13,75,42} -{7,91,3,83,82,37} -{72,91} -{10,67,61} -\N -{43,86,76} -{36,62} -{64,56} -{63,13,22,24} -{76,49,38,23,9,8} -\N -{92,58,24,19,96,90} -{24,37,76,37,1,95} -{91,9} -{46,35,48,37,91,76} -{72,21,6} -{30,80,39,90,89,18} -{83,30,67,17} -{43,36,46,43} -{4,31,34,36,33,48} -\N -{16,49} -{75,56,8,91,4} -{92,80} -{74,72,68,89,7,82} -{79,17,26} -{14,15,28,72,58} -{42,21,9} -{71,39,98,98,61} -{68,63,23,74,74,48} -{91,80,22,100,57,30} -{63,60} -{90,9,10,67,89,14} -{53,93} -{75,49,34,30,38} -{2,43} -{32,4,24,48,23,31} -{45,24,31,15,51} -{65,62,21} -{83,50} -{10,90,98,86,87,1} -{63,2,9,17,30} -\N -{77,46,60} -{49,39} -{37,86,4,63} -{33,28,37,33} -{4,88,80,14,47,45} -{90,64,17,65} -{60,90,12} -{7,2,38,33} -\N -{39,90,7} -{89,32} -{27,47,63,31} -{54,10,10,73,84,87} -{55,58,25,87} -{41,24} -{71,26,8,31} -{74,19,33,81,74} -{47,58} -{44,16,22,59} -{2,10,97,16,25} -{1,98,3,41,6,80} -{12,13} -{3,50,61,85} -{54,5,44,97,71,86} -{54,72,94} -{59,13,28,79} -{73,68,7,13} -{90,49,63,45} -{95,47,84} -{31,79,98,22} -\N -{13,15,83,89,87,20} -{1,58,87} -{15,21,39} -{93,27} -{40,81,13,31} -{29,52} -{28,48,36,41} -\N -{71,23,89} -{29,59,31,45,35} -{49,83,24,19,44,26} -{41,61,36,34,38,88} -{66,17,18,9} -{55,38,93,33} -{84,42,71,15,12} -{11,38,78,80,90,92} -{1,6,28,68,58} -{96,63,73,22,74,29} -{65,97,68} -{92,29,92,36} -{47,25,30} -{25,44,67,95,16} -{7,26,41} -{79,12,44,69} -{17,27,4,60} -{45,30,57} -{68,24,63} -{39,64,94,92} -{27,68,39,68,75,8} -{88,48,48} -{86,86,8,54,7,45} -{93,60,14,90,14} -{97,42,54,67,38} -{13,38} -{84,34,30} -{34,71,77,71,13} -{82,18} -{53,7,79,79} -{28,65,38,20,93,100} -{96,10} -{94,12,93,48,51,20} -{12,4,41,11,25,59} -{95,69,23,25,1,19} -\N -{44,38} -{12,4,96,7,48} -{18,24,52,81,58,77} -{15,36,1,50,81,23} -{39,66,74} -{52,22,99} -{51,11,77,44,22} -{51,19,18,91,75} -{20,17,5,96,63,30} -{31,56,9,21} -{45,70,31,62,9} -{84,22} -{99,62,97,44,87,90} -{95,94,95,24,25,47} -{79,72,57,18,3,26} -{54,67,37,57} -{3,90,9,3} -{95,90,40,7} -{36,70,76,68,14,71} -{15,59,7,1,48} -{91,29,79,62,94} -{76,36,92,82} -{50,79,68} -{55,63,88,87} -{86,89,49,17} -{19,74,14,52,8,59} -{8,58} -\N -{77,74,20,39,26,29} -{38,89} -{58,21,44,81,17,16} -{40,72,12,32,90} -{93,34,92,17,39,85} -{39,2} -{43,21,83} -{81,3,59,28} -{34,97,52} -\N -{84,90,6,74,43,70} -{41,6,10,98,86,41} -{13,72,78,11,37,5} -{100,40,54,75,33} -{66,31} -{58,58,75,83} -{81,90,8,73,87,41} -{9,63,22} -{19,66,19,93,52} -{39,88,13,25,66} -{80,85,66} -{66,76,11,71,97,77} -{70,35,87} -{36,17,69,2,41} -{30,85,65,39,38} -{39,35} -{64,100} -{83,53} -{25,29,29,72} -{19,63} -{32,2,82,15} -{31,31,46,11,2} -{41,1} -\N -{55,41,15} -{18,61,43,22,100} -{47,60,16} -{80,5} -{52,2,76} -{40,26} -{81,12,16,25} -{31,93,89,20,95,75} -{26,75,86,1} -{36,69,70,73,79} -{38,39} -{45,49,52} -{88,53,45,10,49,31} -{21,14,1,83} -{7,71} -{59,38,83,64,44} -{6,52} -{99,99,26,54,47,8} -{13,46,72,5,23} -{7,86,40,73,55} -{28,47,50,62,44} -{32,89} -{39,48,50,100,62,95} -{66,56,11,21,58,59} -{7,44,95,53,95,36} -{83,33,79} -{34,65,51,52} -{67,95,46,45,61} -{69,84,71,38,46} -\N -{24,57,48,27,97} -{83,91,97,94,37,44} -{22,31,38,77,21} -{72,32,53} -{30,45} -{93,94,27,95} -{95,4,79,3} -{33,90,92,54} -{55,8,76,39,85,64} -{82,54,93} -{31,42,5} -{38,14,73,12,14} -{64,13,64,28,32,89} -{5,28,4,22,72} -{37,78,94} -{58,73} -{24,57,33} -{48,28} -{69,42} -{97,91,75,84} -{95,69} -{64,95} -{1,3} -{76,38,81,11,90} -{21,30,54} -{92,100,97,21} -{10,76,64} -{85,79,100,79,76,63} -{13,96} -{91,47,84} -{100,19,45,49} -{99,71,21,10,69} -{19,41,7,63,56,85} -{16,32,6,92} -\N -{62,7,22,65} -{1,86,67,47,83} -{26,2,100,51,1} -{20,22,86} -{74,95,79} -{8,53} -{85,59,61,45,83,8} -{2,76,63,26} -{40,42,84,55,56,23} -{37,7,25,14,2,47} -{86,16,98,41,33} -{76,30} -\N -{16,88,61,4,41,42} -{59,92,94,76} -{96,76,57,62,99,61} -{14,30,23,13,9,32} -{47,49,86} -{48,19} -{73,25,40} -{29,75,31} -{53,26} -{28,95,78,84} -\N -{22,77,13,64,68} -{15,69,82,26} -{42,37} -{64,59,95} -{37,72,86,95} -{9,59,92,57} -{65,37,13} -{93,67,81,54,89} -{21,52,78,59,30} -{98,90} -{17,35,57,4} -{44,56} -\N -\N -{25,26,13} -{62,41,60} -{28,92,16,74,4} -{92,19,85,77,11} -{20,67,85,22} -{75,69,34,29,64,73} -{70,40,2,29} -{87,27,70,54,6} -{10,8,9,62} -{71,41,14,22,23} -{83,79,46,37,99} -{79,42,3,54,20} -{12,60,42,100,39,33} -{13,79} -{95,28,54,52,77,3} -{55,50,25,41,42,16} -{96,67,23,54} -{65,54,32,52,16} -{100,11,69,96,95} -{1,18,93} -{53,78} -{24,40,47,30,40,11} -{87,7,12,10,52,90} -{3,72,95,15,32} -{60,69,19,8,43,72} -{88,10,11,55,37} -{67,48,31,48} -{98,70,38,97,14} -\N -{52,12,94} -{41,26} -{81,65} -{66,74,9,66,12,3} -{47,6,33,92} -{95,2,12,90,73,97} -{23,76,34,23,2,20} -{7,22,37,83,15} -{44,61,21,8,36} -{88,52,8} -{66,3,67,43,87} -{16,51,10} -{66,43,28,69,70} -{47,2,94} -{57,67,55} -{40,59,6} -{63,19} -{51,71,68,28} -{73,97,48,56,70} -{3,4,28,48,18} -{31,94,27,70,44} -{85,18,40,6} -{78,91,79,88,33} -{11,90,78,49,97} -{74,91,27,79,75,53} -{1,70,3,40,43,99} -{97,35} -{58,27,40,6,47,33} -{43,42,60,94} -{41,34,23,53} -{57,44,50} -{8,10} -{49,53,22} -{91,2,90,13} -{46,80,27,82,42,99} -{12,96,72,23,83,56} -{48,82,71,8,35,16} -{38,69,38,49,47} -{80,28,13,9} -\N -{84,13,12,33} -{31,57} -{68,86} -{4,96,64,19,48,29} -{66,8} -{33,86} -{32,38,86,86,41,84} -{38,51,31} -{59,17,76,36} -{52,87,60,54} -{7,58} -{34,52,58,90} -\N -{30,67,97,2,1} -{93,10} -{47,16,46,8,39,84} -{90,77,37} -{92,58} -{38,94,49,53,11} -{70,49,35,67,18,28} -{58,81} -{79,100,9} -\N -{97,13,56} -{99,40,87,67,58} -{24,47,19,16} -{12,27,47,48,3,59} -{1,58,15} -{97,28,6} -{94,50,31} -{71,34,94,53} -{26,5} -{46,66,56,27,37} -{76,4,1} -{80,63,40} -{89,82} -{39,100,71,82,95,8} -{81,86,27,83,57,47} -{30,30,92,8,33} -{95,20} -{4,19,8,74} -{20,32,83,62,19,18} -{75,29} -{100,13,6,41,23} -{63,5,93,72,43} -{64,13,73} -{35,91,61,26,41,96} -{49,56} -{2,28,80,84} -{15,48} -{32,49,96} -{72,73,57,69,16} -{95,1,88,64} -{70,55,88,66} -{76,66,30,92,1} -{88,21,74,65,93} -{72,75,75,3,26} -{55,32,85,68,84} -{45,40,93,33,72,20} -{83,89,6} -{4,60} -{72,56} -{73,7,69,25,96,74} -{100,72,41,48,63,37} -{21,72,70,94,67,54} -{6,9,58,77,35} -{70,59,35,25} -{86,96,87,62,13,5} -{93,52,74,57,58} -{93,23,88,50,56} -\N -{95,72,68} -{63,52,58,41,54,90} -{52,23,53,32} -{93,87,39} -{23,73,6,46,79,72} -{44,17,12} -{79,59} -{31,62,14,26,75,23} -{64,72,18,48,63,50} -{71,40,59,87} -\N -{82,17,10} -{44,29} -{6,4,39,16,21} -{94,17} -{91,61,37,36,9} -{53,38,7,28,92} -{95,93,35,18,48} -{35,77,53,87,97,92} -{56,28,68,19,28,86} -\N -{23,91,56} -{97,5,89,24} -{18,81,17,78,63} -{83,19,46,10,22,66} -{100,17,45} -{25,87,61,79} -{17,57,99,1,39,1} -\N -{2,51,26} -{93,69,84,85,87} -{40,58,70} -{86,84,96,41} -{28,36} -{39,85} -{16,84,75,68,87,17} -{14,84,57} -{25,85,35,82,56} -\N -\N -{7,30,17,2,66,91} -{45,17,57,27,98,65} -{57,86,15,40,68,23} -{82,32,28,89,41,79} -{28,3,35,61} -{76,95,19,81,48,50} -{34,6,85,47,65,2} -{70,23,91,33,15} -{30,24,47,96,61,47} -{78,88,64,60} -{87,40,86,97} -{47,14,54,37,100} -{48,95,32,77,69} -{58,12} -{63,20,49} -{78,85,41,72,6} -{39,20,89,21,62,76} -{71,6,10} -{63,4,71} -{51,21,37,63,54} -{66,6,63,12,58} -{89,97} -{64,70} -{53,1,65} -{57,73,30,26} -{15,99,47,89,95,99} -{12,86,7} -{50,68,1,31,67} -{47,86,54,44} -{78,7,86,76,22} -{46,71,98,62,67} -\N -{64,91,80,63} -{82,61,17,58} -{85,64,90} -{37,26,64,97} -{68,25,26,61,68} -{11,21} -{63,53} -\N -{87,88,75,65,10,48} -{32,7,38,72,44} -{99,81,59,10} -{31,58,60,66,41,28} -{23,27,57,74,4} -{20,94,28,29} -{91,5,15,61,50,29} -{34,58,15,85,65,29} -{52,50,2,95,87} -{3,94,54} -{7,61,96,49} -{51,70,23} -{87,49,27,6,7} -{83,61} -{36,92,48,57,20,83} -{53,12,60} -{60,11} -{68,43,74,23,66,55} -{66,8,54,24} -{48,72,41,74} -{81,99,50,33,20,13} -{27,80,60,83,26,74} -{80,1,59,50,15,99} -{11,70,20,29} -{23,84,63} -{63,24,91,19,28} -{25,17,95} -{94,13,81,69,26,89} -{31,48} -{45,20,74,51,62,33} -{77,55,17,63,4,18} -{89,14} -{85,85} -{23,11,85,74} -{29,76} -{62,40,96} -{1,29,25} -{56,26,12} -{5,22,6} -{61,9,6,85} -\N -{31,34,49,11,19} -\N -{14,20,64,73} -{63,1,85} -{2,58,61,100,9} -{89,92} -{37,13,81,77} -{36,26,16,76} -{78,10,10,92,63} -{68,6,35,71,92,27} -{2,88,33,14,85,27} -{80,95,71,98} -{8,33,33,55,90} -{62,74,15,10,64} -{60,18} -{6,77} -{27,38,4,49,27,89} -{94,84,94,8,98} -{15,73,47,47,26} -{73,38,69,90,9,13} -{17,33,32} -{51,57,25,40,41,37} -{77,70} -{66,10} -{50,90} -{96,88,30,65} -{30,49,100} -{34,46,19,89,52,24} -{83,85,62,72,10,64} -{98,56,23,77,79} -{97,90,83,85} -{19,66,70} -{70,89,59,12,71} -{24,96,22,4} -{43,32} -\N -{92,85,41} -{96,90} -\N -{4,5,82} -{58,32,34,86,30} -{51,8,44} -{31,96,37,47} -{51,15,41,97} -{86,41} -{41,26,61} -{62,79,68,73,5} -{32,9,88,30} -{89,34,64} -{70,18} -{64,31} -{14,73,1,50,75} -{57,1} -{53,92,38,13,56} -{41,1,87,40,60} -{83,75,19} -{69,98,25,64} -{69,75} -{84,13,25,8,81} -{41,52} -{90,80,17} -{19,53,72,62,94} -{29,30,99,32} -{32,85,73,26,47} -{6,48,89,93,23} -{73,47,93,10,48} -{60,21,26,60,63} -{85,41} -{75,61,61,45} -{51,7,5} -{9,46} -{83,36,7,84,96} -{71,78,55} -{43,53,88} -{8,1,80,69} -{88,86,51,12,37} -{45,69,40,85} -\N -{36,53,60,15,7,7} -\N -{92,5} -\N -{51,13,34} -{39,23} -{16,26,93} -{91,96,19} -{89,64,2} -{8,74,29,24,66} -{26,19,30,27} -{81,59,52} -{99,28} -{5,12,63,79} -{14,80,90,83,47,79} -{67,64,32,58,44,19} -{27,32,52,79,55} -{68,87} -{14,31,20,12} -{38,99,65,32,15} -{27,57,35,17,53} -{63,64,6,60} -{70,38,47,65} -{24,87,20,4} -{86,27,19,56} -{62,44,1} -{46,10,26,48} -{40,57} -{61,9,59,80,51,20} -{83,44} -{77,1} -{78,63,42} -{75,93,95,76,9,52} -{20,58,10,37} -{72,75,41,73} -{63,93,5} -{57,65,47} -{34,6,51,38,21} -{54,7,19,9} -{61,6,47,64,100,86} -{39,45,55,17} -{81,53,67,33,70} -{11,94} -{57,98} -{78,81} -{75,71,20,8,13} -{3,2,58,95} -{37,58,5,46,54} -{40,50,36,27,69} -{73,42,86} -{97,73,87,80,38} -{27,56,94,73} -{80,81,74} -{53,79,86} -{79,4,55,21,34,74} -{84,63,21,97,92,38} -{72,38,76,63,97,79} -\N -{64,91,100,98} -{34,10} -{97,73,7} -{49,31} -{87,39,65,96} -{54,88,60,55,18,4} -{20,72,96,26} -{40,51} -{37,46,89} -{88,53,3,52,39} -{10,34,77,95} -{20,66,84,12} -{51,19,61} -{67,35} -{73,56,89,43,35} -{94,54,27,63} -{63,53,21,79,76,49} -{79,23,28,63,49} -{47,94,75,11} -{67,95,56} -{80,86} -\N -{62,73} -{98,69,11,57,24,90} -{87,41,77,21,94} -{21,87} -{3,40,75} -{67,53,78,29,16} -{18,46,70,76,98} -{14,67,50,63,22} -{4,2,92,4,8} -\N -{41,76,79,95,96,61} -{35,30,18,57} -{34,91,89,27} -{22,25,9,34,85} -{4,53} -{23,6,65,86,56,93} -{54,81,8,59,36,47} -{90,10,4,25,31,46} -{91,82,82,80} -\N -{64,12,59,21,10} -{49,93,76,26} -{22,10,21,15,57} -{14,29,93,31} -{68,21} -{62,95,12} -{34,74,55,4} -{26,39,93,31} -{67,31,63} -{23,89,98,88} -{48,93,22,79,28} -{1,88} -{95,74,84,18,38} -\N -{82,29,22,45,15,81} -{15,48} -\N -{17,36,97,77} -{93,59,71,15,51,35} -{67,33,57,11} -{35,80,72,43} -{69,89,69,48} -{52,29,16,52,100,22} -{60,30,45,19,25} -{28,3,39,86,13} -{81,40,25,20,39,5} -{77,14,93,47,23,6} -{42,19} -{52,52,98} -{9,29} -{78,77,6,72} -{2,59,73} -{13,85,77,26,29} -{64,63,94} -{54,76,3} -{7,1,5,91,100} -{24,94,57,94,79,55} -{4,22,1,75} -{34,53,19,87} -{69,75} -{71,47,47,61,42,89} -{3,32} -{84,61,4,13,73} -{74,61} -{47,65,85} -{50,84,83,18} -{51,97,11,3} -{59,92,4} -{49,42,65,27,97,52} -{19,33,40,44,71,100} -{82,68,99,60,47,59} -{47,33,82} -{3,45} -{47,28,60} -{3,98,60,30,50} -\N -{11,40} -{33,67,72,43,74} -{9,49} -{42,47,48} -{53,88} -{17,87,28} -{20,4,72,62} -{65,25,22,76,64} -{9,62,57} -{59,93,52,93,60} -{85,85,1,55,50} -{69,22,57} -{8,50,81,32,4} -{80,47} -{60,88} -{16,54,80,66} -{99,87,66,65} -{60,19,58,18} -{14,77,66,48,59,41} -{75,96,82} -{42,72,93,79} -{14,23,78,82,40} -\N -{29,47,16,41} -{13,11,45,67,23,92} -\N -{8,3,52,41,56} -{57,41,63} -{5,50,59,87,50,58} -{58,99,9} -{60,99,15,63} -{59,14,9} -{68,81,34} -{83,18,3,94,39} -{27,52,100,66,48,82} -{10,23,50,96} -{72,14,12,68,62} -\N -{45,30,55,86,89,48} -{5,80,97} -{52,67,86,81} -{99,4,38,79} -{21,98,78,71,73} -{10,23,38,61} -{12,17,19,70} -{79,23} -{55,66,65,60,19} -{7,34,68,88} -{37,70,5} -{41,57,86,31,10,6} -{70,59,96,78} -{88,18,32,22,56,21} -{93,72,81,47,89,72} -{100,14,49} -{83,80} -{73,11,97,14} -{60,47,32,34,13,29} -{39,6,88,24,6} -{54,66,55,52,47} -{56,89,88,98,94,48} -{2,37} -{13,54} -{68,39,68} -{60,81,10,85} -{74,54,14} -{30,52} -{41,74,47} -{77,28,8} -{90,3,43,89,4} -{29,46,84,63,79,83} -{26,15,80,19} -{76,28,77,6,47,91} -{51,15} -{93,15,51} -{8,68,34,58,15} -{5,56,57,81} -{27,87,61,54,41} -{31,37} -{68,80,3,98,49,6} -{96,10,39} -{25,19,21,72,79} -{69,1} -{5,51,61,80} -{76,25} -{36,92} -{54,46,31,87,13,8} -{25,13,83,57} -{29,53,73} -{83,60,26,19} -{27,89,34,13,20,38} -{29,74,26,67,65} -{90,36} -\N -{32,15,43,50} -\N -{55,86,68,51} -{91,14,53,70,49,38} -{75,29,79} -{19,59,38,44,18,79} -{43,31,24,20,16} -{43,83,59,37} -{61,17,95,61} -{67,89,1} -{65,20,46,58,49} -{72,54,38,52,49} -{75,12} -{63,95} -{99,17,79,11,35} -{62,60} -\N -{69,83,89,73,20} -{30,60,39,73} -{78,99,29,45,61,21} -{38,61} -{51,15,47,11,4} -{34,75} -{57,26,42,42} -{8,90,4,68} -{63,70,99,3} -{74,70,33,50,59} -{27,18,73,83} -{36,90} -{82,77,2,83} -{90,99} -{15,25} -{65,30,39,82,89,34} -{12,24,64,54,49,83} -{54,59} -{63,49,81,36,75,52} -{6,59,90,55,87} -\N -{97,52,54,97,3} -{8,53,89,42,30} -{68,42,64} -{97,42,99,74} -{19,31,32,52,7} -{69,83} -{61,17,35,39} -{81,47,70,7,63} -{78,10,63,97,31,48} -{84,92} -{64,82,40,39,57,44} -{39,25,92,33,5} -{27,74,85} -{90,67,21,28,84} -{36,33,62} -{77,87,98,82,11,88} -\N -{11,41,17,91,56} -{1,1} -{84,100,8,22,20} -{57,39,85,5} -{55,47} -{13,2,36,59,45} -{95,66,53,32,29} -{21,92} -{35,32,9,58,77} -{19,71,99,82} -{19,37,87,43} -{100,18} -{67,86,29,40} -\N -{66,54,64,55} -{67,25,18,31} -{60,26,59,86,26,67} -{26,21} -{70,67,30} -{93,82} -{89,58,39,91,95} -{15,86,25,8,12} -{59,20,41,33,78,87} -{10,72,89} -\N -{52,17,99} -{77,29,7,7,1} -{49,96,57,24,66,67} -{10,26,83,84} -{82,7,25} -{66,77,57,25} -{92,77} -{24,48} -{44,26,37,75,11} -{73,80} -{51,47,93,21,25,78} -{76,49,15,98} -{12,85,63,59,6} -{25,51,47,58} -{16,10} -{17,30} -{67,5} -\N -{54,96,21} -{12,47} -{29,90,69,22,89,82} -{78,93,86,65,66} -{83,84,58,67,13} -{85,35,81,27,1,2} -{76,29} -{64,82,91} -{35,89,38,89,10} -{19,40,96} -{83,70,85} -{72,85,70,99} -{34,1,39,16} -{84,53,22,86,73} -{32,23,70,49} -{15,67,91,11} -{73,95} -{71,57,64} -{88,91,56} -{12,16} -\N -{62,82,26,84} -{70,51,52,63,96} -{34,93,49,57} -{16,5,47} -{18,59,12,82,83,51} -{61,93,87,9} -{46,9,45,38} -{15,85,28,73} -{31,99,26,3} -{66,91,48,73} -{98,80,9} -{31,55,42,69,13,58} -{43,8,70,29,83} -{39,57,53,70,74} -{89,13,60,38,89,3} -{37,28,15} -{67,77} -{30,100,89,36,53,75} -{36,19,48} -{7,8} -{12,76,26} -{14,56,52,47,39,67} -{87,83,51,2,97,25} -{51,1} -{59,69,37} -{95,93,21} -{100,92,37} -{37,23,66,95,7,63} -{52,56,77,86,46} -{31,62,17} -{57,48,79} -{26,96,40,5,43,54} -{40,92} -{75,83,1,73,71} -{75,61} -{6,38} -{35,23,76} -{52,3,38,25,100,99} -{45,15,44} -{96,9,11,35,16,58} -{9,80,76} -{22,43,34,43,46} -{34,68,21} -{95,70,83} -{60,7} -{34,22,68,2} -{78,30} -{46,70,90,96} -{5,24,69,61,32} -{41,17,79,27} -{59,88,64} -{12,48,41,68,15,98} -{43,84,59,62,36,14} -{84,8,71,88,4,23} -{45,67,67,17} -{14,96,72,66} -{91,23,4,11,28} -{18,5} -{65,51} -{31,87,33} -{17,97,76,81,69} -{56,71} -{95,23} -{33,58,66,47} -{46,99,69} -{43,87,40} -{49,1,26} -{18,36,89,87,25,100} -{76,37,19} -{57,91,9,100,23,59} -{80,60} -{55,23,32,49} -{15,73} -{87,50} -{43,62,50,54} -{65,3,89,49,77} -\N -{73,12,25,78} -{79,89,38,59} -\N -{44,62,25} -{96,13,57} -{35,14,3} -{90,71} -{34,8,59,81,63,90} -{15,90,89,32,69} -{90,61,54,10,29} -{22,3,85,41,66} -{17,4,99,91,45,57} -{89,32,43,39,61,9} -{45,40,6} -{47,100,75,8,85} -{88,43,89} -{45,41} -{54,48,87,66,100,5} -{58,65,39} -{17,82} -{95,14,31,51} -{30,3,46} -{8,66,22,52,51,24} -{61,62,38} -{4,50,83,32,76} -{96,36} -{87,27} -{82,100,44} -{30,91,44} -{29,48,8,38,43,96} -{56,65} -{34,36,99,11} -{11,1,25,65,12,89} -{17,100,62,53,24} -{86,81,63} -{17,63,30,82,87,91} -{12,63,76,78,85} -{52,19} -{21,91,53,86,49,83} -{67,65,78} -{8,77} -{89,1,56,100,72,96} -{20,51,41,21,30,20} -{41,73,37,92,9,5} -{95,34,21,12} -{28,14,2,62} -{14,74,33,32} -{37,82,67} -{65,99,56,11,21,83} -{99,51} -{56,42} -{59,30,74,40} -{18,27,63,44,86} -{48,25,41} -{5,26,63,88} -\N -{24,66,64,1,26} -{72,74,11,61,70} -{28,27,90,30} -{96,35,21} -{64,100,75,94,88,3} -{93,79,42} -\N -{37,51,4,41} -{31,68} -{93,42} -{76,96,47} -{8,6,16,57,51,72} -{67,72} -{50,36,40} -{69,28} -{17,92,40} -{72,74} -{76,87,93,22,95,30} -{14,88} -{39,56,74,36,25,87} -{55,68} -{32,9} -{35,2,17,86} -{92,73,82} -{40,13,95} -{15,28,95} -{65,40} -{47,56} -{63,72,78,20,22} -{71,49,4,80} -{68,16,50,44,29,38} -{81,96,23} -{44,73} -{4,68} -{30,54,41,66,89} -{92,33} -{10,92,49,46,59,42} -{14,91,18,96,27,37} -{40,32,12} -{14,97,15,96,44} -{75,96,52} -{50,20,9} -{39,84,83} -\N -{14,48,3} -{47,85,76,27} -{5,3,25} -{55,36,29,76,41,44} -{34,56} -{62,29,83,6,58} -{67,32,85} -{75,62,4,66,100} -{47,31,27,43,9,57} -{92,44,36} -{31,22} -{14,88} -{18,25} -{82,63} -{54,67,6,59} -{90,42,19,91,37,75} -{70,39,87,52,32} -{51,20,34} -{85,62} -\N -{95,6,55,93} -{44,67,15} -{93,58,20,12} -{42,6,22,29,36} -{46,81} -{57,95,56,52} -{3,79,69,45,8,74} -{75,44} -{4,17,78,96,66,41} -{27,100} -{85,76,22,17,45,58} -{9,12,70,29,96} -{5,68} -{54,79,5,19,17,24} -{99,13,9,52,86} -{94,6,99,57} -{71,62} -{63,50,9} -{42,42,80} -{25,96} -{93,20,10} -{83,73} -{14,76,36} -{57,31,29} -{17,25,18,18,54,95} -{34,27,86,37,92,83} -{57,57,28,32} -{98,53,60} -{8,59,41,88,49,46} -{95,42,30} -{12,51,98,74,76} -{6,49,26} -{21,35,27,32,83,93} -{16,56,89} -{85,34,73,74} -{52,95,22,4,71} -{96,42,63,88,80,91} -{78,34,41,99} -{11,68,27} -{50,14} -{78,52,66,15} -{100,82,1} -{35,2,93,71,45} -{4,56,8} -{83,19,5} -{82,39,63} -{50,64,83,87,76} -{47,59,93,88,22,67} -{16,6} -{86,98,88} -{32,4,52,34,30,71} -{68,25,97} -\N -{19,17,91,84} -{97,88,89,98,33} -{37,56,70} -{27,17} -{56,58,51} -{69,80,47,84} -{89,22,89,88,16,1} -{95,14} -{14,95,97} -{47,15} -\N -{19,20,65,74,83,38} -{57,56} -{78,67,68,89,1,95} -{61,84,93} -{10,56,96,31,56} -{3,51,90} -{15,85,42,25,15,41} -\N -{50,7,89,89,96} -{90,10,44} -{11,43,15,27,30} -{55,68,48,30,44} -{38,69,3,95,39,6} -{57,51,88,94,82,23} -{69,37,2,67,49} -{93,94,5,84,39,47} -{45,47} -{58,55,79,63,64} -{63,65,59} -{42,36,76,75,89,86} -{41,83,98} -{13,90,13,46,11,37} -{76,33,52,65} -{52,29} -{20,60,45,23,29} -{89,6,14,8} -{91,69,64,72,41} -{46,91,31,66,83,33} -{6,58,61,65} -\N -\N -{90,65,16,5} -{24,46,33,36,47,45} -{11,62,40,98,21,88} -{28,95,58,33,27} -{45,63,99,31,38,90} -{11,49,41} -{23,24,82,25,28} -{42,3,34} -{52,10,58,88,97,37} -{20,41,11} -{86,30} -{36,92,93,10} -{5,36,85,50,71} -{51,75,100,46} -{55,81,31,45,87,8} -{83,10,45,81,33} -{16,94,91,23,76,44} -{62,73,14,39} -{16,14,83,100,82,7} -{25,69,86,12,71} -{29,86,45} -{76,62,100,47,57,52} -{41,21} -{33,56,58} -{23,96,44,16,91,86} -{65,15} -{3,92,56,4,21} -{32,39,95} -{95,87} -{65,96} -{16,96,93,100,35,78} -{64,33,55} -{96,75,41,40,62} -{50,50,86,11} -{93,34,83} -{19,30,62,67,93,19} -{53,67} -{55,46,99} -{70,32,38,4,84,91} -{50,36,40} -{21,93} -{29,6,10} -{4,73,45} -{72,33} -{36,73,18,55,27,100} -{65,73,98,90} -{20,1} -{59,36,60,87} -{20,79,63,93,34,31} -{60,18,92,6} -{48,34} -{63,70,78,1,2} -{15,32} -{5,15,84,73} -{32,35,90,11,40,23} -{91,41,7,52} -{84,90,88,30} -{12,10} -{84,86,36,79} -{76,45,84,66} -{41,25,61,96,97} -{18,100} -{63,39,17,34,32} -{22,45,74} -{83,24,45,48,69,84} -{43,41,12,44,75,91} -{69,75,95} -{100,28,14,66,1,14} -{94,91,60,36} -{88,28,54,63} -{68,78} -{29,68,6,100} -{12,84,35,44,59,55} -{30,59} -{64,18,40,57} -{97,97} -{85,64,73,82,49,88} -{99,31,24,6,90} -{23,89,38,20,40,95} -{84,64} -{21,3,91,7,7,87} -{91,74,32,76,43} -{13,22,96,8,75} -{59,71} -\N -{34,94,45} -{14,5} -{95,10,37,74} -{69,82} -{6,58,45,49,81} -{72,72} -{17,58,10} -{62,77,9,6,44,62} -{37,53,49,41} -{24,11,11} -{10,57} -{26,72} -{18,15,83,60,54,80} -{88,49,73,92,67} -{26,88,64,2,59} -{49,50,3,90,44,49} -{58,54,43} -\N -{86,78,40} -{42,17,65} -{1,86,17,6} -{79,27,37,60,8} -{46,62,46,22} -{9,75,17,68,54,35} -{99,86,64,10,20} -{3,21,35,6,24,64} -{25,62,9,50} -{63,2,79,42,81} -{44,41,2} -{99,93,98,78} -{2,92,9,96} -{79,82,25,64} -{47,84,52} -{97,77} -\N -{47,94,38} -{22,33,76} -{35,52,11} -{17,48} -{1,100,27} -{87,93,19} -{72,3,32,78,81} -{47,28,4,23,79} -{27,88,7,85} -{49,40,47} -\N -{91,89} -{80,2} -{86,78,42,6,81} -{7,50,25,4,8,22} -{23,3,64,59,53} -{1,42,63} -{95,81,86,31} -\N -{81,83,52,47,25,43} -{17,57,100,49,59,63} -{44,91,95,72,29,100} -{80,78,55,41} -{14,52,20,64,9,87} -{48,14,82} -{31,5} -{64,50,66,38,97} -{61,2,90,2,64} -{64,69,26} -\N -{64,62,68,89,12} -{12,10,88,71} -{41,66} -\N -{67,77,25,6} -{14,75,15,66,19} -\N -{88,52} -{78,56,61} -{93,88,47,38,52} -{72,100,54,34,18} -{77,99,89,53,25} -{38,51} -{3,25} -{83,39,85} -{60,15,77,59,69} -{38,64,91,97} -{65,35,30,8} -{46,6,48} -{63,91,29,91,85} -{43,100,56,60,74,53} -{95,30} -{86,63,28,62,37,79} -{2,48,29} -{1,44,20,47,56} -{43,34,86,86,64,14} -{11,82,99,71,63,41} -{77,45,74,17,56} -{18,25} -{51,82} -{27,35} -{1,20,84} -\N -{89,37,16,90} -{58,83,34,88,50,21} -{61,25,1} -{41,6} -{9,100,32,54,38,66} -{40,53} -{29,76,16,13,55,31} -{71,67,54,83,3,82} -{19,62,18,94,73,38} -{17,83,8,45,52} -{80,25,50,59,53} -{4,2} -{52,48,6,72} -{50,32,70} -{36,97} -{17,82,36,97,20} -{22,87} -{46,29,96,98,14,90} -{14,92,5} -{69,9,68} -{20,86,29,61,54} -{62,67,87} -{86,18,31,80,82,45} -{65,89,67,34,41} -{44,8,48,38,91} -{47,32} -{85,25,56,39} -{15,54} -{84,57,44,46} -{65,61,29,86,77,53} -\N -{26,58} -{76,1,57,93} -{57,91} -{13,15,66,11} -{84,12} -{43,32} -{83,24,31} -{82,9,65,84,27,94} -{62,93,55,7,39,46} -{90,100,33,22,61,46} -{9,51} -{87,93,82,94} -{49,45,95,95,66,39} -{100,56} -{11,5,78,42,45,37} -{3,57,80,46,13,34} -{1,74,53,31,33} -{11,84,8} -{27,99,21,31,96,58} -{99,81,90,17} -\N -{66,49,47,55} -{88,30} -{76,62,17,88,83} -{40,7,42,61} -{17,57,9,64,54,1} -{9,54,84} -{50,61} -{72,15,25,30,6} -{64,95,69,89,11} -{64,18,86,25} -{81,59,70,6,92} -{78,76} -{33,40,29} -{15,63,1,12,14,57} -{33,81,8,65,26} -{58,15,56,37,67} -{2,50,35,92,11,27} -{17,13} -{91,100,15,27,39,24} -{58,48,46} -{5,95,28} -{7,21,99} -{5,15,6,10} -{82,99} -{66,22,86,83,76} -{99,68,39} -{43,90,22} -{31,94} -{21,64,56,26,95,40} -{7,81,3,53,83} -{29,42,90,60} -{53,49} -\N -{26,31,14,73,88,51} -{69,2,100,9,34,16} -{78,35,97} -{68,16} -{34,45,42,73} -{7,19,55,70,69,11} -{11,62,61} -{32,17,51,33,87,6} -\N -{54,97,36,13,45,12} -{46,2,26} -{14,6,17} -{99,20,31,61,6,4} -{60,72,53,31,34,25} -{88,46,68,78} -{56,94,49} -\N -{33,65} -{70,51,84} -{55,91,27,33} -{22,19} -{34,78,11,94,3} -{16,67,91} -\N -\N -{64,5} -{76,18,83,5} -{57,13,30,56} -{60,92,25,31,43} -{38,17,54,5,2} -{56,58,39} -{42,43,5,69,56,89} -\N -{50,23,97,85,70,39} -{97,56,33,90,64,2} -{9,54,51,26,24,99} -{18,7,59} -{44,5,40,69,18} -{77,96} -{44,58,47,17,26,45} -{90,71} -{88,32,11,96,17,13} -{42,3} -{97,28,56,10} -{38,36} -{50,52,47,31} -{64,5,99,77,83} -{11,56,1} -{91,92} -{7,53,35,52} -{93,65,47,97,44,82} -\N -{64,66} -\N -{62,4,57,23,34,91} -{52,55,75,99,27} -{29,54,44,87,61,96} -{21,3,66,35,25,80} -{96,68} -{3,41,66,81,78} -{49,98,79,65} -{71,38} -{88,79,70,37,3,82} -{49,74} -{19,29} -{57,68,9,8,99} -{81,88,14} -{99,29,24,99} -{55,96,29,89,49} -\N -{56,2,84,79,74} -{30,52,64,74,62,5} -{88,32,19,25,9} -{40,11,49} -{98,52,27} -{11,86,29,86,6} -{91,53,63,53,44,28} -{88,10,30,48} -{75,64,75} -{14,92} -{98,62,35,67,66,35} -{40,65,11,80,73} -{1,1,63} -{85,32,53} -{91,27,68,50,66,63} -{66,54,38} -\N -{45,43,14,94} -{62,84} -{54,24,83,33,46} -{93,72,2} -{43,4,14} -{18,11,5,99,79,94} -{26,59,9,2} -{58,69,70,45,14,54} -{84,5,42,97} -{7,82,41} -{69,53,8,55,20} -{4,13,6,45,83} -{41,92,41,98,51,85} -{72,85,74} -{19,50,79} -{79,47,47} -{25,25} -{17,56,46,30,73,78} -\N -{92,42,83,34,92,29} -{8,52,76,80,9,55} -{80,100,2,52,24,4} -{55,15,92,27,86,50} -{83,79,41,88,86,53} -\N -{44,16,90,54} -{99,20,64} -{44,30,26,26} -{35,35,24,74,72} -{97,24,94,55} -{78,42,32,76,100,98} -{31,86,12,87,72,86} -{87,35,33,88,33} -{31,83,23} -{46,51,5,6,71,31} -{39,97,91,53,39} -{19,18,25} -{16,4} -{65,77,13} -{61,30,13,26,75} -{67,9} -\N -{31,3} -{15,19} -{97,39,71,30} -{12,96} -{36,96,82,62,5,74} -{81,22,46,11,19} -{97,55} -{58,67} -{10,68,79,74,23} -{29,71} -{50,59,8,1} -{12,51,32,7} -{62,16} -{48,82} -{84,21,24,13} -{46,86} -{100,96,32,54,13} -{72,41,3,67} -{61,9,7,75} -{39,44,50,30,38,6} -{63,63,6} -{69,35,6} -\N -{7,91,82,48,55} -{57,22,31,57} -{55,72,91} -\N -{76,98,43,71,10} -{100,34} -{78,53,14,73,23} -{42,90,28,44,44} -{90,34,22,81} -{60,32,56} -{98,53,58,58,61} -{61,70,59,78} -{2,96,27} -{83,99,25,47,13} -{17,54,11,47,70} -{70,43,11,89} -{93,70,82} -{72,57} -{35,95,49,36,19} -{82,25,16,49,43,93} -{2,51,96,48,88} -{20,81} -{74,4} -{66,83} -{90,75,98} -{25,87,59,92,55,96} -\N -{20,80,92,93} -{59,63,39,3,7,38} -{64,10,85,22} -{63,32,18,38,83} -{49,38,83,54,1} -{27,97} -{18,34,84,58,7,86} -{93,4,67} -{43,49,32} -\N -{29,14,5,50,30} -{59,15} -\N -{76,31,31,47,17,35} -{95,41,71,27} -{47,43} -{75,80,56,78} -{56,75,43} -{99,10,100,76,44,1} -{5,31,72,3,25} -{21,90,59} -{59,45,75,93,78,88} -{76,55,4} -{20,87,44,94,56,78} -{38,87,71,13,23} -{33,6,79,91,92,27} -{13,15,31,15,11} -{57,18,57,71,11} -{67,60,64} -{66,15} -{57,45,74} -{93,91,97,30,12,94} -{37,83,62,18,28} -{94,88} -{12,11,85,10} -{42,96,89} -{15,65,5,65} -{52,58,36,27,10} -{72,88,76,50,96} -{40,70,55,93} -{80,33,24} -{53,35,50} -{11,37,55} -{25,80,32,91,68} -{11,2,52,39,37} -{17,51,45,44,85,84} -{81,21,77,15} -{67,93,27,70,72,94} -{86,99,95,98,83,28} -{9,65} -{1,26,5,23,5,17} -{57,82,42,60} -{46,67,65,98,69,79} -{41,50,94} -{77,81} -{87,82,18,57} -{88,27} -\N -{32,58,81,88,94,90} -{23,37,65,38,29} -{61,11,65,77,25} -{50,53} -{38,2,11,9,27,94} -{64,9} -{1,45,97} -{61,41,67,46} -{13,41,90,15,80,82} -{83,6,9,22,25,37} -{95,74,22,64} -{16,17,4,80,66,33} -{25,42,43,84,96,85} -{25,93,50,87,6} -{35,67,90} -{82,37,59} -{4,44,83,2,81} -{78,46} -{64,79} -{18,41,3} -{56,20,51,83} -{26,77,52,70,93,13} -{54,53,12,47,57,63} -{94,48} -{39,12,41,5,3} -{28,33,93} -{20,29,9} -{75,38,10} -{96,54,96} -{47,87} -{19,35,11,3,80,72} -{75,56,84,24,55,48} -{58,5,13,6} -{10,53,32,6} -{23,8,59} -{71,2,35} -{41,16,99} -{77,6,16} -{30,27,56,85,11} -{47,21,93,82} -{50,68,85,34,19,57} -{14,76,58} -{78,81} -{68,99} -{19,79,67} -{91,73,82,88,44,36} -{49,18,75,32} -{54,18,99,74,9} -{51,58,60,30} -{99,86,83,22,88} -{24,42,76,30} -{86,16,54,69} -{37,39,72,45} -{92,62,3,36} -{31,80} -{43,22,11,15} -{38,88,95,25,49} -{92,21,10,28,47,55} -{99,18} -{26,64,72} -{29,12,17} -{54,69,49,84} -{57,42,4,61,10} -{60,85,74} -{24,29} -{91,71} -{96,49} -{47,51} -{88,67,59,18,86} -{32,18,64,54,41,27} -{78,100} -{77,30,85,93,2,20} -{80,90,68} -{49,37,5,42} -{88,12,94,51} -{85,65,2,41} -{60,38} -{87,37,20} -{27,81,94,37,54,84} -\N -\N -{38,74,78,78,89} -{3,100} -{42,80,68} -{34,17,96,91} -{7,29,83,71,87,26} -{28,81,76,8,43,48} -{74,11} -{28,85,84,78,59,69} -{30,22} -{3,83,75,60,78,11} -{20,62,18} -{74,69} -{91,44,50,62} -{57,18,9} -{14,48,21,33} -{91,1,53,58,92,51} -{64,41,90,52} -{81,95,38,78,7,44} -{65,25,15,90,40,51} -{66,41,31} -{5,92} -{17,98,7,57} -{97,36,99,77,50,88} -{96,56} -{40,62,88,8,53,62} -{18,91,63,93,94} -{88,79,43} -{31,87,98,85} -{12,88,58,53,77,38} -{83,10,37,69,1,7} -{13,47,66} -{85,33,39,48,6,39} -{74,87} -\N -{26,50,26} -{48,78,10,39,17} -{27,43} -{58,17,18,80} -{86,43,58,77,67} -{53,12} -{9,79,9} -{85,79,89,88} -{35,77,22,52} -{93,64} -{47,52,90,17} -{75,15,25,68,28} -{35,6,68,37,18,53} -{80,14,2,89,4} -{52,49,5,66,59,44} -{5,26,96,1,84} -{71,8,61,19,72} -{17,94,84,72,55,83} -{72,10,16,40,17,75} -{6,70,15} -{22,99,7,19} -{55,19,4} -{6,47,69,42} -{17,9,63,44,15} -{23,20,72} -{10,80,20,87} -{99,3,23} -{11,76,8,77,58,38} -{45,14} -{22,89,73,63,54,9} -{16,19} -{1,26,29} -{92,20,65,33,16,40} -{27,64} -{22,19,95} -{36,16,9,30,31,14} -{40,50,68,52,77,58} -{35,15,11} -{67,2} -\N -{63,48,76,25} -{14,65,42,60} -{61,58,31,51,70,4} -{35,41,72,29,46,62} -{98,48} -{90,23} -{1,79,80} -{10,5,54,59,16} -{15,1,9,75} -{34,100,90} -{73,76,25,77} -{98,82,77,67} -{79,5,20} -{9,69,9,52,2} -{23,22,77,80,79} -{32,51} -{23,52,5,33} -{95,20,96,78,48} -{100,37,6,15} -{98,1,53,20,97} -{5,28,26,78,33} -{19,75} -{49,42,30,72} -{50,98,56,26,87} -{76,59} -{51,16,18,48,46,97} -{80,60,51,43,58,28} -{23,12,70} -{40,16,14,18,46,21} -{72,79,47,57,23} -{7,17} -{49,95,6} -{14,24,29,13,90} -{82,28,34,55,15,87} -{31,24,3,50,45} -{86,95} -{97,22,17} -{27,14,27} -{61,63,31,74} -{55,81,87,67,90} -{81,9,79} -{100,29,43} -{41,88,37,29} -{62,57,16,91,60,65} -{94,90,34,94,27,48} -{15,36,80,30,23,90} -{47,91,6,42,93} -{53,74,5} -{84,14,56} -{30,56} -{10,12,92} -{33,7,75} -{96,39,50,77} -{89,85} -{20,39,63,22,44,18} -\N -{90,23,79,91,85,8} -\N -{73,70,52} -{75,100} -{27,4,29,96,25} -{56,31,80,59} -{1,91} -{16,67} -\N -{17,88,59,41} -{13,49,29,76,71,9} -{41,38,16,29,66,40} -{68,67} -{39,74,47,71,63,80} -{4,74,33,92} -{17,60,82,7,52} -{62,88,39,19,22} -{77,21,1,95,42,2} -{98,62} -{55,17,81,31,11,88} -{73,52,18,94} -{16,64,90,33} -{87,41,81,95,85} -{20,55,96,75} -{71,72,11,11,83} -{75,94,89,47,41,7} -{56,48} -{76,29,74,31,67} -{47,70,68,36,70} -{5,69,10,94,54,32} -{29,96,71} -{64,28,86,58} -{82,57} -{42,2} -{64,48,59,8,45} -{61,69,43,40,1} -{69,84} -{68,51} -{32,20} -{21,7,5,60,35} -{100,40,18,98,37} -{50,96} -{87,10,12,27} -{47,3,46,43} -{60,87,10,31} -{92,87,50,37,72,73} -{99,61,77,87,29} -{23,95,31} -{96,100,43} -{17,64,84} -{13,19,57} -{65,86,4,75,46,69} -{49,60,99,37,50,11} -{77,82,88,12} -{12,95,66,98,63} -{83,78,68} -{76,14,87,25,29,14} -{20,9,99,73,67} -{42,51} -{36,22,33,6,63} -{53,46,22} -{40,89} -{37,7,89,17} -{32,89,16} -{65,87,4} -{16,16,57,35} -{34,90} -{80,54,1} -{11,93,34} -{5,19,31,50,99,33} -{98,1,33,54,7} -{45,39,23,78} -{37,47,98,83,10,5} -{55,88} -{42,76,18,99} -{86,31,25,5,45} -{67,87,47,1} -{23,15} -{78,88,66,96} -{58,55,41,67,86,41} -{21,53} -{90,14,28,38,95,71} -{20,5,13,52,1,88} -{29,98,50,75} -{91,3,24,75,82} -{62,33} -{56,69,31,95,66} -{46,85,40} -{17,22,67,57,39,16} -{58,25,92} -{31,53,82,64,69,40} -{40,12,30,1,39} -{78,10,42,40,25} -{58,27,1,12} -{28,11,80} -{36,89,69} -{50,95} -{61,63,59,62} -{51,77} -{90,24,88,84} -{61,27,57} -{51,81,33,75,48} -{47,30,33,23,44} -\N -{79,51} -{62,44,5} -{98,83,80} -{31,33,89,69,19,40} -{22,38,61} -\N -{90,70,10} -{37,90,49,65,95,52} -{95,42,4,47} -{92,100,43,31,27,1} -{39,17,88,20,2,80} -{82,64,36,84} -{31,18,21,18,52,34} -{3,35,36,33} -{26,39,69} -{67,63,66} -{54,85} -{65,71} -{26,14,84} -{63,82,73,30} -{66,79,21} -{71,13} -{57,25,40,14,22} -{63,9,91,31} -{70,63,36,32,93} -\N -{11,85,47,31,54} -{34,47} -{42,78,92,85} -{75,64,12,83} -{33,98,52,91} -{22,25,91,79,33} -{33,51,20,77,23,65} -{83,66,46,24} -{54,65,31} -{43,41} -{52,47,66} -\N -{59,85,85,63,83,53} -{16,76} -{44,97,48,52} -{26,36,72} -{26,55,98,7} -{70,88,7,87,62,37} -{11,42} -{98,38,36,72} -{51,90,82,33,92} -{59,80,79} -{76,77,18,71} -{34,56,62} -{85,12,37,66} -{34,64,74} -{77,63,28,76,11} -{2,63,87,50} -{60,98,60,19,15,57} -{93,66,33,71,36,3} -{41,94} -{62,72,87,19} -{57,83,36} -{63,64,21,13,70,32} -{71,36,9,55,34} -{92,52,90,45,88} -{59,54} -{4,51} -{55,25,35,90,93,2} -\N -{75,15} -{25,86,43,18,77} -\N -{31,40} -{55,49} -{67,1,84,20,9} -{15,1,48,18,100} -{62,46} -{4,39,86,55} -{49,17} -{65,20,71,49,55,49} -{40,57,63,14,3} -{48,68} -{67,97,58,55,5,34} -{3,73} -{79,97} -{82,63,87,66,32} -{19,49,96,50,55} -{32,19,41} -{17,53} -{64,81,70} -{66,75,18,92,54,93} -{7,94,38,86} -{16,62,45,19,10,11} -{18,47} -{58,96,69} -{65,25,58,98} -{29,51,37,40,44} -{91,78} -{37,84,85,65} -{70,61,31,22,32,22} -{67,12,99,39,78} -{41,79,46,54,84,22} -{38,26,43,4,45,75} -{29,68,35} -{69,59,69,33} -{4,46,52,49} -{1,25,44,12,71,29} -{38,75,99} -{83,58,86,6} -{93,35,35,34} -{85,26} -{15,46,95,60} -{62,63,65,49,10} -{44,67,19,80,83} -{63,41,30,43,85} -{13,46} -\N -{13,95,1,34,72,37} -{4,32,22,47,6} -{67,65,77,3} -{40,70,22,44} -{74,9} -{44,28,5,32,67,51} -{55,14} -{41,3,72,68} -{64,82,72} -\N -{11,88} -{91,90,92} -{68,66,95,80,58,54} -{30,49,11} -{54,86,59,69,67} -{56,83,36} -{15,67,9,47} -{92,30,78,2,87} -{12,54,2,1,59,36} -{84,25,67,38,19,53} -{28,45} -{54,84,9,75,59,26} -{47,35,54,93} -{36,96,59,75} -{78,78,52,93} -{87,96,67} -{5,61,15,13,27} -{53,58,6,78,86} -{43,70} -{72,38,15,61,58} -{75,27,30,12,35,71} -{18,72,35,62,81} -{45,10} -{36,91,73,25} -{81,85,22,34,29} -\N -{15,97,82,44,19,83} -{51,23,18,6,74} -{53,75} -{62,9,73,95,37} -{58,42,33,41,71} -{5,97} -{30,2,89,81,93,61} -{32,3,18,84,24} -{6,97,20,89,23} -{27,74} -{22,86,81} -{77,19,42} -{92,9} -{58,90,59,91,30,54} -{29,51,92,34} -{85,68,59} -{36,83,75} -{37,50,86,9} -{79,70} -{33,46,93} -{97,17,6,88,10} -{18,42,88,4} -{41,95,71,27,95} -{8,2,81,56} -{54,94,54,28,70} -{34,87,20,10,5} -{36,76,87,5,100} -{97,91,25,89,89,95} -{76,26,73} -{82,23,7,42,58,72} -{53,16,99} -{10,34,57,47,2,96} -{81,93,26,19} -{8,1} -{79,55,37,61,62,3} -{34,16,69,58} -\N -{41,7,99,87} -{70,21,86} -{59,2,49,45,91,97} -{37,2,74,2,61,68} -{97,39,15,4,13,1} -{67,71,8} -{51,2,84,38} -{55,8} -\N -{75,27} -{37,36,49,70,82,41} -{70,20,85,89,99,90} -{69,61,100,49,75,35} -{11,4,67,4,91,17} -{77,56,65,78,25,8} -{16,58,6} -\N -{88,38,19,88,27,27} -{12,46} -{36,67} -{62,33,96,94,80,96} -{56,94,12,1,65,54} -{58,73} -{19,80,27,72} -{47,55} -{14,91} -{94,75,92,32,19} -{99,12,91,4,85} -{56,55} -{86,83,77,66,66,87} -{46,68,13,45} -{49,75,62,35,39} -{20,25,33} -\N -{91,47,56,68,14} -{88,43,24,42,4} -{50,24,94,18} -\N -{71,54,91,66,97,22} -{81,16,19,67,6} -{78,46,81} -{63,93,71,75,87} -{90,38,10,85,12} -{11,24,93,42,25,77} -{30,14,32,67,70} -\N -{86,91,77} -{73,74,64,66} -\N -{7,18} -{85,94} -{37,15,55,100,59} -{55,18,44,79,57} -\N -{52,40,97,75} -{60,53} -{38,9} -{27,67,77} -\N -{43,83,82,24,35,64} -{22,75,29} -{9,19} -{67,1} -{15,35,11} -{65,45,95} -{65,9} -{63,84,99,89,6,77} -{20,44,31} -{82,50,88} -{29,12,46,21,98,7} -{98,71,3,73,6,86} -{61,44,74,2,45,33} -{16,56} -{31,87} -{72,30,37,94} -{65,30,82,17,12} -{86,19} -{55,76,96,61} -\N -{44,92,83} -{41,22,79,95,20} -{36,33,86,9,61} -{22,88,8,57,73,30} -{63,97} -{36,53} -{56,52,48} -\N -{35,8,3,93} -\N -{53,52} -{7,48,78,46,70,14} -{33,92,55,17} -{39,57} -{71,43,72,7} -{92,85,55,38,35} -{68,30,67,8,18,92} -{9,85,82,24} -{46,46,19,14} -{96,97,31,59} -{35,99} -{54,7,20,28,29} -{20,21,56,82,19,40} -{2,39} -{33,49,63,49,93} -{35,40,26} -{30,35} -{94,70,2,23,91,74} -{34,37,72,19,15} -{92,21} -{72,63,64,35,40} -{59,11,9} -{24,3} -{93,75} -{22,14} -{63,99} -{39,47,10,14,3,45} -{51,74,5,85,70} -{6,33,15,4,89,20} -{97,82,29,15,66} -{47,47} -{88,79,57,10,68} -{18,22,13,100,100,67} -{75,50,9} -{3,12,34} -{39,51,20} -{56,5,63,18} -{83,44,86,46,37} -\N -\N -{60,16,54,75,62} -{91,95} -{39,55,11} -{37,7} -{29,49} -{38,4,52,85,67,38} -{36,56,2} -{52,14,92,39,77,16} -{42,25,49,55} -{70,10,33} -{53,46} -{83,15,28,59} -{35,69,82,4,58,46} -{73,55,64,9} -\N -\N -{60,25,8,8,39} -{50,71,61,64,64} -\N -{65,67,67,34} -{77,59,18,64,16} -{43,72,32,44,59} -{55,57} -{12,47} -{30,75,89,81} -{23,92,16,31} -{64,45,21,74,19} -{4,47,49,47,96} -{37,14,20,18,87} -{61,45,38,39,1,87} -{4,98,99,52,27} -\N -{23,6,50} -{22,61,46,79} -{90,54,60,9,49,42} -{73,27,51,72} -{73,11,23,60} -{7,31,52,34} -{27,68,39} -{39,8,21,48,64} -{86,64,92,60} -{55,36,40,46,23,46} -{32,79,86,44} -{72,29} -{33,87,57} -{57,87,61,22} -{67,84} -{32,99,26,92} -{22,27,34,82,8} -{99,25,99} -\N -{29,75} -{39,63,25,45,7} -{39,67,18,13,18} -{23,83} -{77,69,22} -{60,13,46} -{2,10,42} -{37,20,27} -{30,21} -{85,15,52} -{6,89,38} -{68,22,26,37,96} -{6,85} -{93,51,63,46,26,64} -{79,77,15,26} -{90,6,39} -\N -{50,58,85,27} -{69,8,72,47} -{7,59} -{55,16,54,95} -{96,5,50} -\N -{77,92,13} -{46,30} -{43,65} -{17,65,32} -{10,6,46,1,47,75} -{48,82,71} -{63,12} -{68,14,10,97,34} -{15,45,58,100,7,74} -{9,23,88,1,95} -{61,60,15,12,58} -{84,51,46,41,71,26} -{58,62,39} -{86,67,31} -{32,31,89,2,30} -\N -{90,74} -{65,79,76} -{22,30,77,47,40,23} -{67,99,56,73} -{11,24,30,93,89} -{70,17,65,78} -{100,6,67,29} -{39,4,22,59} -{84,29,70,9} -{74,43,72,27,55,27} -{12,39} -{1,83,100} -{48,23,9} -{21,88,21,35,16} -{92,34,44} -{91,96,13} -{93,57,40,79,81} -{86,3,94,82,43} -{78,70,19,97,49} -{47,22,98,36} -{20,59,65,54,81,27} -{58,13,73,19,54,96} -{26,20} -{70,75,14,70,82} -{77,67,53,33,83} -{2,43,36} -{84,17,28} -{68,25,95,62,92} -{47,90,15,69,85,23} -{92,92,24,37} -{96,14,14,38,38} -{80,4} -{66,86,28,15} -{18,90,74} -{93,76} -{64,96,14} -{76,41,86,67,64} -{58,95,2,86} -{12,60,96,70} -{22,37,58} -{1,67} -{75,23,24,7} -{3,57,66} -{57,30,68,100} -{68,57,33} -{26,32,65,51,75} -{40,14,60,97,83} -{88,96,42} -{66,21,21,78,34} -{15,56} -{86,60,66,66,16} -{94,6,58} -{99,63,70,57,10} -{82,59,62,38,82,51} -{48,61,9,46,28,57} -{29,23,61} -{12,30,42,20} -{99,65,24,7,97} -{20,5} -{6,49,85,56,97,4} -{62,93,88,86,75,29} -{46,2,94} -{57,71,45} -{38,60,21,78} -{95,53,92} -{61,1,88} -{67,80,49} -{59,82,1,48} -{19,94} -{25,64,16} -{96,73,50,85} -{28,17,46} -{81,51,50,18} -{57,99,66,93} -\N -{23,62,57,94,40} -{21,6,83} -{4,11} -{83,16,50} -{46,41,23,1} -{4,15,8} -{86,51,29,80} -{48,34,55,81,89} -{5,2,43,67,66} -{42,59,37,91,1} -{14,98,27,80,33} -{18,58} -{49,93,60,91,94,88} -{32,62,64,63,48} -{51,1,90} -{56,8,68,49} -{16,34,79,18,76} -{66,88,41} -{31,66,93,44,96,40} -{100,99,30} -{37,49,95,91,18,43} -{95,2,94} -{84,15,70,31,30,84} -{31,41,45} -{9,73,2,7,34} -{17,35,43,1,25,72} -{8,70,8} -{1,93,32,16,71,61} -{98,51,27,56,46,65} -{1,11,57,72,33,7} -{48,96,64,55,75} -{83,82} -{7,74,70,29,59,60} -{29,44,5,77,52} -{84,58} -{87,63,62,52,69} -{29,58,32,11,13,17} -{35,99,67,67,93} -{54,31} -{53,24} -{58,59,32,22} -{8,76,23,63,94,54} -{3,88,75,17,64,91} -{29,30} -{3,81,39,9,77,82} -{77,85,59,56,8} -{47,12,63,13,40} -{66,81} -{67,33} -{39,46,28,79,95,67} -{49,13,98,63,10,58} -{14,42} -{80,70,60,92} -{63,54} -{30,70} -{60,89,14,62} -{56,40,94,55} -{70,31,46,20,95} -{18,65,89,7,75} -{60,33,80,43,37,4} -{85,19,98,79,36,84} -{69,1,48} -\N -{30,87,9,22,99,60} -\N -{23,96,9,85} -{22,94,39,58} -{30,38,4,97} -{16,70,62,5} -{35,52} -{32,10,72} -{35,34,40,31,66,80} -{7,77,14,48,97} -{67,64,37,22,69} -{51,53} -{67,71,90} -{87,71,45} -{44,84} -{19,58,11,34,45,85} -{68,19,55} -{27,16} -{7,14,92,22,33,46} -{47,2,49,53,63,32} -{15,39} -{13,47,84} -{29,74,97} -{51,74} -{70,26,46,33,51} -{31,86,14,23,61} -{20,85} -{21,10,57} -{90,94,59,72,97} -{97,30,74,84} -{15,89,69} -{11,40,2} -{68,19,47,28} -{47,65} -{2,7,52,53,44} -{40,74,34,36,78,71} -{22,60} -\N -{37,75,47} -{53,78,2} -{4,32,42} -{35,76,69,88} -{95,13,3,38,3} -{74,74,62,90} -{8,72,42,2} -{11,43,5,43,70,16} -{69,19} -{61,37,26,49} -{16,100,69,32,35} -{58,77,26,76} -{74,87,37,47,84} -{8,82,29,93,15} -{74,88,93,85,97,95} -\N -{29,23,99,98,36,93} -{8,36,87,64} -{71,90,43} -{7,28,78,46,52} -{62,25} -{33,90,7} -{60,72,39,18,86} -{98,59,73,24} -{17,69,2} -{49,16,63,56} -{13,37,62,1,95} -{98,89,69,92} -{50,26,34} -{90,16} -\N -{40,54,3,79,51,19} -{29,24} -{6,12,82,24} -{92,52} -{89,2} -{64,25,68,55,81,2} -{64,77} -{71,46,58,50,56,34} -{94,17,35,30,60,33} -{37,30,2,40} -{98,15,16,92,2,50} -{44,19,82,57} -{37,34,6} -{59,43,1,53,79} -{7,37,14,14,92} -{80,78,49,81,23,17} -\N -{91,51,12,35,79} -{9,14,2,84} -{62,3,77} -{25,5,40,12,40,79} -{65,88,82,94,89,90} -{20,35} -{80,71,83} -{6,9,83} -{94,58} -{2,76,55,61,42,53} -{60,53,45,82,3} -{1,37,75,96} -{82,61,81,10} -{36,46,1,31,90,45} -{22,55,11,25,21} -{69,13,29,20} -{95,54} -{16,79,82,67} -{4,58,84,84} -{52,7} -{25,14,94} -{69,8,67,54} -{30,71,36} -{81,78,23,38,76,58} -{86,59,61} -{11,42,63,74,99} -{66,4,55,34,16} -{39,57} -{10,81,9,8,21,10} -{75,55,64,97,7,45} -{8,46,86} -{39,100,52} -{30,51,7,13,54} -{72,85} -{10,52} -\N -{61,7} -{93,1} -\N -{74,31,3} -{90,96,26,84} -{88,58,74} -{28,45,74,24,74} -{95,88} -{42,70,43,64,22} -{46,83,48,36} -{81,99,100,43,11} -{47,24} -{46,67,63} -{26,15,36,89} -{90,11,78,70,81,87} -{65,90} -{89,99,21,81,47,38} -{37,42} -\N -{94,51} -{12,57,95,63,29} -\N -{68,99} -{27,8} -{16,52,11} -{72,5,85,44,57,51} -{11,6,91,7} -{87,80} -{94,61,1,38,77,89} -{93,60,6,98,46} -{52,47,44} -{93,66,61,22} -{7,61} -{15,83,93,91,12,40} -{66,3,5,72,72,36} -{67,72,68} -{42,42} -{38,17} -{75,60,47,39} -{58,28,51} -{61,8,61,81,65} -{46,52,97,84,27,47} -{97,53,47} -{64,93,83,72,27} -{34,79,34,36} -{25,5,92,37} -{12,20,55,94} -{17,43} -{39,37,16,70} -{79,62,15,16,64,28} -{80,87,96,41} -{51,55,1,94,72} -{75,22,56} -{2,55,7,20,39} -{8,91} -{73,8,42,73,31} -{90,90,23} -{82,68} -{63,64,68,12,59,19} -{100,80,23,24,17} -{23,46} -{25,13,31} -{43,95,54,85} -{40,62,21,21,82} -{70,20,16} -{90,11,23,18} -{16,9} -{51,57,30,27,21} -{50,55,75,77,53,33} -{84,92} -{14,66,32} -{44,100,16,30,82} -{41,48,58,60,7,44} -{81,76,13} -{18,26,82} -{84,35,15,98} -{52,84} -{13,80,36,35,28} -{91,16,71,55} -{87,89,6,20,28} -{12,75,92} -{48,41,55} -{59,75,26} -{48,19,48,72} -{91,4,100,25,17} -{46,52,97,78,94} -{7,81,76} -{54,54,49} -{89,37} -{78,22,57} -{75,25,83} -{25,89,10,38,96} -{52,12,1,74,35} -{13,48,88,7} -{6,97,20,19,91} -{53,2,99,76} -{4,58,46} -{30,30,89} -{97,2,87,47,55} -{14,11,72,83,97,74} -{44,69,11,51} -{47,17,86,27} -{15,19,56,96,24,94} -{81,67} -{11,11} -{20,94,49,36,39} -{39,78,40,46} -{33,87} -{76,89,58} -{94,74,25} -{33,77,5,47,55} -{28,67,99,81,93,83} -{31,10,19,65,60} -{53,25,74,24,48} -{73,69,23,45,88} -{70,56,41} -{21,73,72,28,99,5} -{75,69} -{78,99} -{66,49,89,86,2} -{30,53,18,21} -{67,69} -{1,98,38} -{91,25,16,39} -\N -{75,54,93,39,18} -{96,84} -\N -{64,71} -{6,15,78,50} -{8,45,26,15,25} -{8,90,94} -{52,66,13,98,86,69} -{3,25,28,56,88} -{84,72,89} -{10,33,46,6,57,100} -{13,91,99,2,49} -{83,59} -{88,64,42,50,77,16} -{81,12,27,45} -{12,17,31,93,22,53} -\N -{28,84,85,35,3} -\N -{42,12,86,76,37,63} -{46,23,18} -{45,80,76} -{94,18,100} -{17,80,84,80} -{84,88,29,16,10} -{7,42,90,51,33,40} -{79,51,22,2} -{31,30,72,24,23,84} -\N -{55,50} -{69,47,82,29,83} -{94,56,69,18} -{7,81,71} -{95,13,32} -{66,59,68,62} -{52,19,62,51,80,32} -{38,18} -{73,24,81,58,22} -{11,59,41,19,96} -{61,11,56,89,89} -{61,72,9} -{63,12,8} -{76,54,75,84,6,44} -{74,3,11,62,30,74} -{46,60,71,55} -{28,47,52,71,33,33} -{35,51,37} -{38,89,40,29,30} -{18,26,99,89} -{36,44,8,100,72} -{1,23,6,5,23} -\N -{84,17,16,44,81} -{29,70,24,85} -{23,57} -{20,98,30,23,1,66} -{82,3} -{70,7} -{15,49,58} -{19,40,70,88,35} -{45,10} -{62,89,47,71,55} -{34,100,88,44,3,91} -{92,65,16,24,7,9} -{20,12,61,95,7} -\N -{57,49,42,87,88,14} -{89,99,86,31} -{32,55,51,78} -{55,66,78,10,12} -{37,19} -{13,5,36,66} -{89,7,40,45} -{41,58,41,24,11} -{98,8,9,27,40} -{49,83,89} -{91,36,78,44,100,62} -{76,78,9,52,57,27} -{100,59,37} -{51,1} -{92,83} -{45,1,85} -{8,81,45,94,32} -{52,26,9,98,7} -{97,52,4,85,13,11} -{94,38,58,4,72,91} -{5,39,26,14,74,51} -{31,44,37,24,89} -{8,74} -{56,93,36,3} -{23,46,25,90,42} -{4,98} -{31,95,27,26,20} -{3,7,79,9,90} -{29,22} -\N -{35,34} -{80,28,12,21} -\N -\N -\N -{36,49,94,83,25,9} -{6,62,89,93,59} -{67,75,3,93} -\N -{94,62,3} -{97,36} -{43,89,26,94} -{46,56,22} -{50,15} -{45,47,39,61} -{23,32,24,45,43,11} -{97,66,29,8,52,67} -{37,1,48} -{30,84,86,91} -{4,46,59,35} -{76,37,41,90} -{26,28,92,27,88,17} -{76,37,27,41} -{74,51,31} -{16,33} -{66,85,68} -{4,81,72,62} -{65,14} -\N -{11,43,28,14,9,43} -{60,88,95,1} -{52,92,69,48} -{37,81,85} -{57,73,8,79} -{50,26} -{52,41,99,6,33} -{9,34,58,22,9} -{56,37,19,77,50} -{93,21,18,90,41,40} -{28,89,76} -{4,36} -{89,54} -{70,28} -{66,11,3,47,30,43} -{69,54,86} -{45,41,57,34,18} -{91,46,32,68,42,68} -{25,87} -{75,57,12} -{55,15,68} -{6,63} -{22,39,88} -{77,39,10} -{39,49,69,61,66,77} -{78,25,42,73,89} -{17,47,36,27,79} -{33,83,44} -{27,75,12,96,94,87} -{50,17,95,42,25} -{67,13,22} -{59,85,95,2} -{81,57,83} -{25,11,72} -{32,84,97,6,65,52} -{62,25,24,27,50} -{80,64,23,74,54,75} -{97,17,15,100} -{50,11,41} -{57,82,40} -{10,90,41,52,39} -{4,11,86} -{79,17,51} -{48,100,92,77,58} -{88,67,19} -{40,96,52,35,16} -{89,63,32,81,28,63} -{44,56,66,50,55} -{28,73,46} -{32,40} -{52,65,85} -\N -{51,34,18,82,83} -{49,49,90,71} -{84,16,74,78,86,10} -\N -{73,9,47} -{51,59,49,90} -{85,13,78} -{98,77,18,15,92,85} -{40,94,66,94} -{89,51,80,12} -{23,26,75,17} -{96,2,51} -{88,62,90,32} -{85,19,87,89,30,15} -{33,38,9,46,19,87} -{27,45,15} -{39,79,82,88} -{31,33} -{41,64,10,1} -{35,61,22,76,74} -{75,11,90,16} -{71,23,43} -{35,3,97} -{88,4,97} -{100,61,28} -\N -{64,74} -{9,44,81,98,55} -\N -\N -{76,89} -{18,34,80} -{77,83,91,50,20,41} -{65,50,26,65} -{79,18,90} -{5,60} -{42,21} -{31,70,80} -{20,98,15,14} -{58,65,45,6,64} -\N -\N -{88,82,98} -{75,81,32,34,59} -{37,14} -{30,36,55,70,65} -{84,55,26} -{56,64,1} -{31,41,89} -{46,43,43,90,34,100} -{78,36,21,14,69} -{100,10,45} -{73,69} -{60,86,5,70,78,99} -{6,89,92,8} -{86,68} -{44,4,71} -{41,36} -{95,80,42,94,34} -{73,29,50,49} -{61,20,57,17,36} -{37,58,67} -{56,83,77,37} -{98,67,40,10,35,76} -{54,84,6} -{7,71} -{65,74,43,6} -{62,98,74} -{81,26,17,22,47} -{49,32,59,35,11,94} -{80,50} -{91,1,50,97} -{71,35,84} -{97,4,46,45,8,36} -\N -{81,62,76} -{69,78} -{89,3,16,64,17,17} -{78,72,26,88,81} -{25,34,9} -{50,27,34} -\N -{55,44} -{61,51,39,53,44,46} -{23,94,32,92,90} -{91,47,67} -{1,13,76,57,63} -{77,19,73,18,95} -{100,82,87,6,83,23} -{69,58,48,97,60,50} -{4,83,85,6} -{3,5,91,37,94} -{91,72,31,32,80} -{57,23,39,46,50,20} -{92,28,53} -{71,27,46} -\N -{59,73,29,21,89,30} -{1,83,96} -{34,41,65,35} -{52,89} -{62,68,80,7} -{82,82} -\N -{11,2,62,46,28,9} -{9,16} -\N -{22,44,73,82,39,86} -{97,52} -{46,36,76,56} -{17,97,26,72} -{16,78,9,70} -{65,55,30,91,16} -{27,45,76} -{17,5,90} -{86,52,93,89,42,27} -{51,70,41,35,1} -{91,57,66} -{53,59,62,57,52,56} -{100,100} -{32,78,87} -{61,57,74} -{86,79} -{55,94,64} -{81,20,26,22,23} -{9,96} -{86,65,35,19,88} -{1,37,90,51} -{79,47} -{93,93} -{32,85,69} -{49,12,6,69} -{6,44,92,37} -{28,42,57,28,2,69} -\N -{63,90,25} -{53,28,74,42} -{83,79,94,37,64,69} -{93,100,57,84,80} -{39,93,80} -{97,92,55} -{27,6} -{20,100} -{19,66,3,66} -{7,76,15} -{7,56,92,11} -{61,76,6,98,52} -{20,46,51} -{12,77,45,67} -{78,79,32,22,21,47} -{62,35,1} -{86,66,57,10,47,43} -{43,24,76,18,87,68} -{39,52,71,35,87} -{81,78,8,10} -{33,70,53,54} -{25,77,27,68,95} -{29,53,89,62,51} -{21,76,33,72,39} -{13,22} -{1,1,51,73,20} -{26,97} -{64,75,23,94,62,68} -{25,20,84,57,27} -{26,7} -{92,80,17,48,72,73} -{73,49,88} -{24,36,70,53} -{7,79} -{80,58,33,25,91} -{19,43,61} -{54,49,73} -{51,88,4} -{9,32,5,83} -{17,68,90,15,30} -{98,50,42} -{29,52} -{32,41,4} -{33,97,69,34} -{94,2,60,5,83} -{23,86,43,74,35} -{63,37,38,58,39,14} -{56,7,82} -{88,81} -{50,75} -{78,49,67,68} -{10,61,58} -{84,35,20,30} -{36,34,48,31,16} -{35,7,47,22} -{98,40,56,43} -{16,4,7,9,44,55} -{86,90,30,80,47,91} -{34,91} -\N -{12,67,77,23,11} -{94,8} -{5,68,31,82} -{26,65} -{51,19,86} -{55,83,39,39,96,51} -{31,22,70} -{20,50,15,93} -{1,55,64} -{8,2,14,3,40} -{2,71,25,41,5,5} -{98,61} -{21,64} -{100,76,99,18,78} -{17,4,69,97,61} -{52,79,97} -{52,26} -\N -{90,54,2,62,11,51} -{33,12,34,45,2} -{91,63,51,42,82} -{100,79,73,70,54,14} -{57,94,81,55} -{13,18,94,17,16,34} -{58,79} -{90,64,68,46,95} -\N -{37,46} -{91,94,10,85,100,24} -{65,86} -{94,89,7} -{72,79,77,53,95} -{65,19,92} -{41,79,53,8,63} -{28,60,50,42,9,32} -\N -{6,23,97,23,10} -{12,28,16,39,70,50} -{26,97,61,48,79,23} -{38,98,21,34,65,89} -{29,13,36,19,13,45} -{72,65,58,81} -{43,98,84,5} -{79,41,100} -{35,30,69,42} -{59,13} -{65,90} -{40,38,21,23} -{2,19,26,38,66} -{5,16} -{84,85,97,84} -{34,26} -{87,17,21,32,29,25} -{75,66,87,90,18} -{84,32,29,51,71,68} -{57,25,73,24,53,2} -{74,16,92} -{99,60,19} -{98,14,70,72} -{24,34} -{37,34,81,100} -{67,10,17,60,16,55} -{39,58,5,23,85,95} -{75,93,19,31,47} -{13,27} -{42,14,32,90} -{59,79,70} -{48,96,45,38,58} -{96,87,84} -{23,70} -{25,31,81,36,75,32} -{64,49} -{30,18,38} -{69,27} -{76,82,43,96,73,17} -{84,95,97,12,20} -{57,69,36} -{60,79,19,67,9,12} -{32,39,3,21} -{55,83,51,48} -\N -{37,11,98,53,11} -{2,73,24,18,77,74} -{69,96,17,49} -{53,2} -{1,76,72} -{35,93} -{35,36,36,25} -{59,77,30,13} -{35,69,36,31} -\N -{20,23,51} -{81,83,57} -{87,43,40,56,81,64} -{24,63} -{29,51,45,93} -{73,85} -{59,1} -\N -{13,57,14,11,34,91} -{69,1,4,28,77} -{63,68,41,53,64,43} -{11,1,46,40,6,88} -{51,19,77,10,86,66} -{74,40} -{25,54,46,62} -{94,17,64,15,20,36} -{100,71} -{63,66} -{33,88,5,92} -{92,86} -{91,69,75,13,20} -{57,22,32,33} -{72,87,44,64,46,6} -{50,56} -{36,23,7} -{74,63,3,6,14,29} -{91,42,8,11,49} -{32,64,94,88} -{91,78,55,27,59} -{2,20} -{52,95} -{57,59,35} -{51,15,52,24,14,13} -{64,16,18} -{50,98,71,10} -{92,99,92,80,77,73} -{96,12,70,85,54,73} -{10,44,30,77} -{29,47} -{40,55,62,58,30} -{59,93,7,21,6,20} -{58,91} -{5,70} -{36,23,58,80} -{16,93,54} -{20,8,97} -{78,32} -{10,31} -{24,10} -{56,14,28,10,45} -{1,79,53} -{56,58,86} -{93,83,17,89,93} -{12,4,26,45,97,17} -{42,67,17,13} -{31,90,59,38,4,20} -{86,52,67,10} -\N -{49,59,10,25} -{69,88,31,38,7,36} -{84,21,57} -\N -{60,8,19} -{35,81,66,96} -{13,95,54,38,31} -{27,25,34,11,65,64} -{54,43,20,20,65,95} -\N -{19,27,100,69,43} -{91,8} -{30,65,98,87,84} -{83,85,100,16,20,18} -{80,48,56} -{61,5,92} -{14,94,43,91} -{35,52,60,43} -{73,25,26,61} -{66,41,39,16} -{2,96,90,37,99,92} -{25,31} -{72,57,50,82} -{40,69,5} -{98,34,66} -{90,44} -{34,78,93,15,65,71} -{98,1,28,36} -{16,59,79} -{88,1,14,45} -{41,91,87,20,72} -{46,9,81,90,63,32} -{2,84,29,56} -{2,57,92,69,63,46} -{3,32,76,62,36} -{11,81,3,81,90,16} -{36,1,42,51} -{29,86,53,51,85} -{17,66,16} -{4,21,25,17,65,92} -{13,26,33} -{74,6,46} -{69,19} -{47,78,85,46,41} -{41,62,100,85} -{22,71,66} -{28,15,58,84,22,92} -{68,82,82,85,15,54} -{34,58,72,35,99} -{51,100,40,13,61} -{80,89,94,31,96} -{48,29,33} -{32,85,75} -{76,43,17} -{79,70,3,64} -{76,64,85} -{94,90,3,85} -{86,21,1,8,54} -{87,92,30,36,59} -{20,51,62,17} -{81,61,86,96,47,67} -{5,75,97} -{60,24,79,3} -{85,49,49,48,61} -{66,60,58,92,88,90} -{2,18} -{42,54} -{42,83,68} -{98,76,42,25,90,32} -{64,36,39,45,34,95} -{56,43,78,10,63,18} -{51,40,98} -{85,11,74,41,14,25} -{37,12} -{76,32} -{6,77,16,86,36,25} -{23,93,18} -{75,51,67,29} -{22,9} -{18,58,25,88} -{95,31,12,20,62,54} -{23,97,89,63,73} -{77,41,11,27} -{91,86,97,98} -{84,6} -{74,69,55} -{58,42,92,65,52} -{77,31} -{8,91} -{5,83} -{64,48} -{1,37} -{51,4,49,97,64} -{29,70,3,62,57,1} -{91,8,31} -{86,71} -\N -{61,50,8,6,59,76} -{83,8,54} -{50,45,66,86,52} -{75,48,18,88,82} -{1,52,60,78,45} -{46,65} -{53,2,63} -\N -{89,97} -\N -{75,23} -{30,58,13,50,2} -{59,73,52,8,70,39} -{20,35,77,34,10} -{55,86,14,74,14} -{67,46,48} -{20,9} -{20,92,62,75,34,98} -\N -{72,14,18,46} -{48,71,92,17,31,13} -{47,46,42} -{42,75,14,86} -{97,55,97,78,72} -{8,4,96} -{44,13,13,18,15} -{16,40,87} -{87,66,79} -{14,44} -{35,79,25,57,99,96} -{23,66} -{90,49,24,11,8} -{50,3,24,55} -{60,94,68,36} -{11,20,83} -{66,100,47,4,56,38} -{36,34,69} -{41,57,15,32,84} -{32,25,100,45,44,44} -{70,32} -{15,37,67,63,71,34} -\N -{81,62,20,91} -{32,62,1,68,86,54} -{20,91,40} -{79,69,22,98,14} -{45,42,24,2} -{30,53,15,62} -{81,100,42,20,96,42} -{93,19,7,59,100,49} -{25,7,18,64} -{11,27,1} -{89,67,65} -{39,97} -{47,62,30,61,58} -{4,11,83,18} -{38,30,95,58,13,81} -{83,6,33,73,64} -{89,51,77,45,58,16} -{13,11,88} -{96,79,71} -\N -{18,66,83,52,84,76} -{52,17} -{74,95,16,5,16,51} -{21,20,16,39,84,71} -\N -{75,47,36} -{65,45,12,5,100} -{41,74,84,21,73} -\N -{8,90,46,39,30} -{47,84,42,49,17} -{76,100,35,89,17} -{61,53,50,31,8} -{94,53,20,33,15} -{97,46,62,85,74} -{8,59,40} -{95,71,21,41,85,81} -{55,71,20,74} -{70,95} -{61,42} -{83,74,25,84,18} -{56,43,46,40} -{42,78} -{95,48,98,93,35,98} -{77,34} -{4,54,58} -\N -{13,54} -{87,66} -{12,88,90,95,6,95} -{65,20,10} -{62,74,59} -{49,17,51} -{14,17,65,3,27,41} -{43,42,43,46,79} -{88,75} -{21,46,84,95,31} -{17,17,28} -{32,73,29,11,46,94} -{3,34,81} -{80,83,1,92,69,100} -{9,24,56,17} -{3,80,57,36,14,94} -{39,89,54,17,31} -{70,19,67,21,31,72} -{82,48,68,52} -{96,81} -{92,18,39,50,18} -{6,54,27,52,28,100} -{23,40,7,74,93,50} -{87,51,38,88} -{98,42,43,30,8,71} -{33,26} -{20,21,83,35,99,100} -{28,77,94,32,1,13} -{17,15} -{35,100,9} -{42,6} -{16,28,55} -{7,94,81,60,91} -{100,63,21,28} -{65,20,35,16,76} -{95,3,88,62,1} -{73,44,46,13,55,69} -\N -{60,49,71,77} -{93,39,75,63,69} -{97,36} -\N -{77,16} -\N -{57,30} -{39,31,56,51} -{62,78,62,38,54} -{69,86,99,10,12} -{11,43} -{60,70,83} -{83,82,3,1,60} -{24,55,61,85} -{65,72,13,77,79,100} -\N -\N -{28,97,71,78,68,95} -{34,1,72,79,84} -{10,49,91,44,27,51} -{15,48,80,37,69} -{42,46,32,34,86} -{80,21,26,50,5,8} -{61,71,100,78,54,50} -{36,20,80} -{67,40,47,68} -{60,7,36,36,55,2} -{32,91,13,98,88} -{15,56,65,23,13} -{20,66,81} -{19,36,99,54,86,92} -{82,28} -{43,32,91,37,70,68} -{71,78,82,50} -{1,31,23,48,10,12} -{88,96,1,44} -{27,49,97,29,89,35} -{63,72,58} -{79,9,32,64} -{75,67} -{46,31,83,54} -{66,24,6,89} -{82,10,64} -\N -{19,31,52,34,89} -{16,36,11,12,23} -{55,50,6,20} -{81,72} -{71,74,8,6,31} -{6,20,96,80} -{95,85,56,91} -{36,33,88,12,50} -{77,44,52,50,50} -{94,12,7} -{97,44,40,43,8,21} -\N -{61,14,40,75,87} -{43,21,67,66} -{46,19,80,12,46,28} -{56,11,14,59} -{31,94,50} -{45,26,61,15} -{84,45,44,82} -{9,16,86,54,93,30} -{50,39,37} -{35,60,64,55,73,90} -{61,65,87,20,30} -{12,59,44} -{23,8,97} -{30,59,7} -{85,32,14,95,38} -{18,91} -{10,40,20,8,58} -{5,58,4,94} -{100,11,96,70} -{66,72,7} -{5,31,89,89,4} -{81,68,44,37} -{22,22,76,67,72} -{22,26,30} -{73,47,27,18,54,30} -{44,13,73,95,83} -{18,93,72} -{30,22,73,13,16} -{14,11,66} -{45,33,59,72,92,81} -{97,82} -{30,4} -{1,9,46,70} -{47,50,20,71,48,60} -{26,62,53,70,63,49} -{39,26} -{47,94,9} -{55,3,18,1,75,22} -{42,87,74,57,60,55} -{95,46,21,38,27} -\N -{13,35,48} -{24,39,24,67} -{44,83,49,72} -{22,8} -{77,39,87} -{37,41,44} -{100,57} -{48,54,58,79} -{14,84,40} -{11,51} -{23,80} -{80,82,43,59,2} -{92,53,56,44,90,66} -{44,67,78,9} -{43,91} -{70,74,100,69} -{12,5,75} -{65,51,22,65,56,36} -{52,54} -{38,78} -{30,45,38,99} -{18,88,88,63,51} -{61,24,53} -{72,24,77} -{61,46} -{11,83,49,86,27,60} -{86,60,83,34,33,28} -{65,15,10,51} -{98,92} -{49,49,60,3} -{58,56,43} -{19,25,15} -{24,40,36,49,61} -{5,62,9} -{72,8,71} -{64,85} -{72,84,67} -\N -\N -{80,87,30,70,21} -{30,86,95,19,21} -{17,90,15,89,81} -{40,51} -{77,88} -{14,89,82,62} -{40,66,93,16,55,45} -{22,46,31,17,4,71} -{8,41,88,94,25,61} -{80,8,23,71,59,53} -{61,70,23} -{2,4,79,6,67} -{27,70,42,68,33} -{46,27,10} -{1,93,42,12,8} -{31,9,19,32,62,15} -{16,42,81} -{56,29,12,17,61} -{52,100,98,42} -\N -{29,38} -{49,40,47,63,22,4} -{99,70,13} -{70,28,67,100} -{37,75,65,63,35} -{45,67,37,28} -{42,78,71,39} -{33,35,76,69} -{65,84,57,63} -{17,12,86,23} -{31,62,79} -{3,22} -{85,81,59} -{38,5,15,100,1,27} -{36,96,93,46,75} -{44,61,85,70,71} -{79,72,86,71,77,9} -{23,51,47} -{4,59,48,38,44} -{93,54,86,98} -{60,29} -{49,38} -{54,84} -{72,25} -{51,40,25,27,68} -{24,17} -{95,3,82,31,95} -{56,37,57} -{15,84,98,16,53} -{47,36,15} -{27,36,76} -{38,82,26} -{47,70} -{60,89} -{59,73,99,7,28,89} -{87,49,70,76} -{71,93,76,81,11,46} -{74,87,92,24,43,22} -\N -{26,1,85} -{18,73,43,94} -{92,2,73} -{5,58,85} -{20,7,39,18,59,90} -{11,16,19,77,60,56} -{77,1,95} -{4,4,11} -{48,40,56,74,96,29} -{71,1,62,69} -\N -{34,61,26} -{86,75,13,73,28} -{17,35} -{100,29,37,26,47} -{69,36,52,61} -\N -{81,51,54} -{54,78,46} -{1,78,96} -{33,54} -{72,9,37,30,100} -{67,10,52} -{77,19,74} -{52,27,41,37,98,73} -{8,74,86} -{4,40,99,6,59} -\N -{98,43} -{74,91} -{69,45,73,59,19} -{87,43,31,85} -{2,51,54,3} -{45,73,8,86,4,40} -{2,51,96} -{74,5,8,64,1,46} -{5,64,86,63,12,75} -{6,62,71,24} -{56,84,54} -{61,37,79,63} -{81,39,78,23,86,74} -{50,79,34,23} -{85,36,78,80,19} -{34,94,1,46} -{5,23,38,4,78,2} -{85,100,80,13,73} -{48,86,9} -{47,22,65} -{49,81,18,52,36} -{84,85} -{89,15,71,88,44} -{1,21,81,52,2} -{53,18,7,53,50,11} -{91,89} -\N -{20,6,20,70,12,32} -{98,94,70,52,41,35} -{43,25,2,63} -{95,86,6,82,2,41} -{79,24,63} -{12,96,7,18,48,67} -{55,35,4,75,28,39} -{48,46,33,75} -{10,99,5,5,98,25} -{43,87,5,53,76,64} -\N -{100,13,9,4} -{4,35,65,56} -{27,74,88} -{59,66,10} -\N -{59,85,39,48,17,29} -{59,42,17} -{27,99,12,21} -{9,10} -{15,4,80,25,67,59} -{12,89,96} -{50,32,92,49} -{40,74,10,6,26,43} -{80,71,29,54} -{74,82} -{22,25,27,65,12} -{84,88,53,43,75} -{84,16,51,84,46} -{10,9,44,95} -{87,19,22,10,44,80} -{18,20,87,41,86} -\N -{9,64,4,33} -{65,87,23,65,32,92} -{50,2,23,68} -{29,8,82,28} -{54,92,6,2,28,70} -{23,11,65,78,34} -{77,85} -{30,49,59,8,60} -{77,30,34} -{55,73} -{89,68,55,81,8,81} -{54,28} -{35,22,67,63,48} -{43,37,46,56,81} -{16,78,32,81,77,37} -{35,80,41,76} -{4,93} -{3,32,23} -{43,18,50} -{87,5} -{30,40,91} -{36,69,17,82,70,57} -{73,71,47,63,58} -{24,11,36} -{2,72,61,76,9} -{61,97,10,85,92,56} -{5,44,47} -{24,57,79} -{69,39,97,8} -{78,16} -{62,52,17,35,28} -{48,79,66,64,36} -{14,72,75,30} -{17,21,41,25} -{28,100,66,56,15} -{89,3,32,86,6} -{67,34,16} -\N -{48,27,70,60,1,40} -{69,34,36,46,95} -{59,24,84} -{44,21,90} -{22,30,5,62,13,58} -{79,67,44,10,1} -{67,8} -{40,48} -{64,5,65,35} -{74,45,75,15,31,69} -{42,3,49,33,52,97} -{86,59,69,84,53} -{64,64,41,64,99} -{47,95,16,78,73,68} -{54,11,52,90} -{54,62,79,58,96,59} -{28,34} -{52,94,17,42,9} -{94,22,77,7,56} -{72,24,47} -{6,11,3,23} -{9,6,97,82,40,39} -{73,47,57,8,7,97} -{27,26,1,2} -{64,45,38} -{71,6,6,83,33} -{78,28,40} -{25,8,17,15} -{24,67,53} -{72,42} -{66,25,56,36,32,93} -{18,11,22} -{88,9,75,23} -{20,32,24,44,51,34} -{76,86,11,7,1,61} -{11,77,41,55,87,59} -{62,53,94,46} -{77,20} -{74,97,59,78,9} -{7,94,26,18,77} -\N -{49,59} -{72,22,42,89,14,80} -{49,14,38,19} -{43,88,25,58,39,24} -{21,34,37,65} -{85,3,46} -\N -{11,60,86,65,49,83} -{51,98,7,28} -{85,17,34,59,14,86} -{89,81,48} -{67,40,11,60,75} -{13,45,42,22,82,82} -{98,21,89} -{30,63} -{35,45,68} -{9,29} -{43,71} -{82,44,59,72,48} -{1,48,29,44,14,11} -{75,33,85} -{7,32,92} -{62,14} -{29,31,1,36,51} -{92,12,28,20} -{13,67} -{88,72,14,22,61,42} -{15,98,49} -{65,27,9,76} -\N -{15,95,26,12,52,40} -{17,20,74} -{57,63,15,22,38} -{93,71,8} -{26,84,82} -{20,52,3,3} -{72,95} -{10,9,80} -{9,9,18,51} -{74,24,63,63,57,89} -{64,91,95,18,15} -{64,37,20,36,74} -{52,9,53,6} -{17,31,42} -{3,73,92,13,62} -{57,81,58,49} -{52,56,2,26,18} -\N -\N -{90,90} -{16,92} -{66,51,7,19,10} -{100,81,69,86,95} -{48,64,81} -{87,54,73} -{6,80,100,24,26,8} -{44,67} -{27,94,2,25,34} -{80,25} -{12,2,77,75,15} -{63,14,30} -{85,75,59} -{72,73,54,44,25,76} -{95,44,69,91,62} -{94,73,78,5} -{28,52} -{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 deleted file mode 100644 index d1b440f5a9b..00000000000 --- a/contrib/intarray/expected/_int.out +++ /dev/null @@ -1,377 +0,0 @@ --- --- first, define the datatype. Turn off echoing so that expected file --- does not depend on contents of seg.sql. --- -\set ECHO none ---test query_int -select '1'::query_int; - query_int ------------ - 1 -(1 row) - -select ' 1'::query_int; - query_int ------------ - 1 -(1 row) - -select '1 '::query_int; - query_int ------------ - 1 -(1 row) - -select ' 1 '::query_int; - query_int ------------ - 1 -(1 row) - -select ' ! 1 '::query_int; - query_int ------------ - !1 -(1 row) - -select '!1'::query_int; - query_int ------------ - !1 -(1 row) - -select '1|2'::query_int; - query_int ------------ - 1 | 2 -(1 row) - -select '1|!2'::query_int; - query_int ------------ - 1 | !2 -(1 row) - -select '!1|2'::query_int; - query_int ------------ - !1 | 2 -(1 row) - -select '!1|!2'::query_int; - query_int ------------ - !1 | !2 -(1 row) - -select '!(!1|!2)'::query_int; - query_int --------------- - !( !1 | !2 ) -(1 row) - -select '!(!1|2)'::query_int; - query_int -------------- - !( !1 | 2 ) -(1 row) - -select '!(1|!2)'::query_int; - query_int -------------- - !( 1 | !2 ) -(1 row) - -select '!(1|2)'::query_int; - query_int ------------- - !( 1 | 2 ) -(1 row) - -select '1&2'::query_int; - query_int ------------ - 1 & 2 -(1 row) - -select '!1&2'::query_int; - query_int ------------ - !1 & 2 -(1 row) - -select '1&!2'::query_int; - query_int ------------ - 1 & !2 -(1 row) - -select '!1&!2'::query_int; - query_int ------------ - !1 & !2 -(1 row) - -select '(1&2)'::query_int; - query_int ------------ - 1 & 2 -(1 row) - -select '1&(2)'::query_int; - query_int ------------ - 1 & 2 -(1 row) - -select '!(1)&2'::query_int; - query_int ------------ - !1 & 2 -(1 row) - -select '!(1&2)'::query_int; - query_int ------------- - !( 1 & 2 ) -(1 row) - -select '1|2&3'::query_int; - query_int ------------ - 1 | 2 & 3 -(1 row) - -select '1|(2&3)'::query_int; - query_int ------------ - 1 | 2 & 3 -(1 row) - -select '(1|2)&3'::query_int; - query_int ---------------- - ( 1 | 2 ) & 3 -(1 row) - -select '1|2&!3'::query_int; - query_int ------------- - 1 | 2 & !3 -(1 row) - -select '1|!2&3'::query_int; - query_int ------------- - 1 | !2 & 3 -(1 row) - -select '!1|2&3'::query_int; - query_int ------------- - !1 | 2 & 3 -(1 row) - -select '!1|(2&3)'::query_int; - query_int ------------- - !1 | 2 & 3 -(1 row) - -select '!(1|2)&3'::query_int; - query_int ----------------- - !( 1 | 2 ) & 3 -(1 row) - -select '(!1|2)&3'::query_int; - query_int ----------------- - ( !1 | 2 ) & 3 -(1 row) - -select '1|(2|(4|(5|6)))'::query_int; - query_int -------------------------------- - 1 | ( 2 | ( 4 | ( 5 | 6 ) ) ) -(1 row) - -select '1|2|4|5|6'::query_int; - query_int -------------------------------- - ( ( ( 1 | 2 ) | 4 ) | 5 ) | 6 -(1 row) - -select '1&(2&(4&(5&6)))'::query_int; - query_int -------------------- - 1 & 2 & 4 & 5 & 6 -(1 row) - -select '1&2&4&5&6'::query_int; - query_int -------------------- - 1 & 2 & 4 & 5 & 6 -(1 row) - -select '1&(2&(4&(5|6)))'::query_int; - query_int ------------------------ - 1 & 2 & 4 & ( 5 | 6 ) -(1 row) - -select '1&(2&(4&(5|!6)))'::query_int; - query_int ------------------------- - 1 & 2 & 4 & ( 5 | !6 ) -(1 row) - -CREATE TABLE test__int( a int[] ); -\copy test__int from 'data/test__int.data' -SELECT count(*) from test__int WHERE a && '{23,50}'; - count -------- - 403 -(1 row) - -SELECT count(*) from test__int WHERE a @@ '23|50'; - count -------- - 403 -(1 row) - -SELECT count(*) from test__int WHERE a @ '{23,50}'; - count -------- - 12 -(1 row) - -SELECT count(*) from test__int WHERE a @@ '23&50'; - count -------- - 12 -(1 row) - -SELECT count(*) from test__int WHERE a @ '{20,23}'; - count -------- - 12 -(1 row) - -SELECT count(*) from test__int WHERE a @@ '50&68'; - count -------- - 9 -(1 row) - -SELECT count(*) from test__int WHERE a @ '{20,23}' or a @ '{50,68}'; - count -------- - 21 -(1 row) - -SELECT count(*) from test__int WHERE a @@ '(20&23)|(50&68)'; - count -------- - 21 -(1 row) - -CREATE INDEX text_idx on test__int using gist ( a gist__int_ops ); -SELECT count(*) from test__int WHERE a && '{23,50}'; - count -------- - 403 -(1 row) - -SELECT count(*) from test__int WHERE a @@ '23|50'; - count -------- - 403 -(1 row) - -SELECT count(*) from test__int WHERE a @ '{23,50}'; - count -------- - 12 -(1 row) - -SELECT count(*) from test__int WHERE a @@ '23&50'; - count -------- - 12 -(1 row) - -SELECT count(*) from test__int WHERE a @ '{20,23}'; - count -------- - 12 -(1 row) - -SELECT count(*) from test__int WHERE a @@ '50&68'; - count -------- - 9 -(1 row) - -SELECT count(*) from test__int WHERE a @ '{20,23}' or a @ '{50,68}'; - count -------- - 21 -(1 row) - -SELECT count(*) from test__int WHERE a @@ '(20&23)|(50&68)'; - count -------- - 21 -(1 row) - -drop index text_idx; -CREATE INDEX text_idx on test__int using gist ( a gist__intbig_ops ); -SELECT count(*) from test__int WHERE a && '{23,50}'; - count -------- - 403 -(1 row) - -SELECT count(*) from test__int WHERE a @@ '23|50'; - count -------- - 403 -(1 row) - -SELECT count(*) from test__int WHERE a @ '{23,50}'; - count -------- - 12 -(1 row) - -SELECT count(*) from test__int WHERE a @@ '23&50'; - count -------- - 12 -(1 row) - -SELECT count(*) from test__int WHERE a @ '{20,23}'; - count -------- - 12 -(1 row) - -SELECT count(*) from test__int WHERE a @@ '50&68'; - count -------- - 9 -(1 row) - -SELECT count(*) from test__int WHERE a @ '{20,23}' or a @ '{50,68}'; - count -------- - 21 -(1 row) - -SELECT count(*) from test__int WHERE a @@ '(20&23)|(50&68)'; - count -------- - 21 -(1 row) - diff --git a/contrib/intarray/sql/_int.sql b/contrib/intarray/sql/_int.sql deleted file mode 100644 index 52313ef7a17..00000000000 --- a/contrib/intarray/sql/_int.sql +++ /dev/null @@ -1,84 +0,0 @@ --- --- first, define the datatype. Turn off echoing so that expected file --- does not depend on contents of seg.sql. --- -\set ECHO none -\i _int.sql -\set ECHO all - ---test query_int -select '1'::query_int; -select ' 1'::query_int; -select '1 '::query_int; -select ' 1 '::query_int; -select ' ! 1 '::query_int; -select '!1'::query_int; -select '1|2'::query_int; -select '1|!2'::query_int; -select '!1|2'::query_int; -select '!1|!2'::query_int; -select '!(!1|!2)'::query_int; -select '!(!1|2)'::query_int; -select '!(1|!2)'::query_int; -select '!(1|2)'::query_int; -select '1&2'::query_int; -select '!1&2'::query_int; -select '1&!2'::query_int; -select '!1&!2'::query_int; -select '(1&2)'::query_int; -select '1&(2)'::query_int; -select '!(1)&2'::query_int; -select '!(1&2)'::query_int; -select '1|2&3'::query_int; -select '1|(2&3)'::query_int; -select '(1|2)&3'::query_int; -select '1|2&!3'::query_int; -select '1|!2&3'::query_int; -select '!1|2&3'::query_int; -select '!1|(2&3)'::query_int; -select '!(1|2)&3'::query_int; -select '(!1|2)&3'::query_int; -select '1|(2|(4|(5|6)))'::query_int; -select '1|2|4|5|6'::query_int; -select '1&(2&(4&(5&6)))'::query_int; -select '1&2&4&5&6'::query_int; -select '1&(2&(4&(5|6)))'::query_int; -select '1&(2&(4&(5|!6)))'::query_int; - - -CREATE TABLE test__int( a int[] ); - -\copy test__int from 'data/test__int.data' - -SELECT count(*) from test__int WHERE a && '{23,50}'; -SELECT count(*) from test__int WHERE a @@ '23|50'; -SELECT count(*) from test__int WHERE a @ '{23,50}'; -SELECT count(*) from test__int WHERE a @@ '23&50'; -SELECT count(*) from test__int WHERE a @ '{20,23}'; -SELECT count(*) from test__int WHERE a @@ '50&68'; -SELECT count(*) from test__int WHERE a @ '{20,23}' or a @ '{50,68}'; -SELECT count(*) from test__int WHERE a @@ '(20&23)|(50&68)'; - -CREATE INDEX text_idx on test__int using gist ( a gist__int_ops ); - -SELECT count(*) from test__int WHERE a && '{23,50}'; -SELECT count(*) from test__int WHERE a @@ '23|50'; -SELECT count(*) from test__int WHERE a @ '{23,50}'; -SELECT count(*) from test__int WHERE a @@ '23&50'; -SELECT count(*) from test__int WHERE a @ '{20,23}'; -SELECT count(*) from test__int WHERE a @@ '50&68'; -SELECT count(*) from test__int WHERE a @ '{20,23}' or a @ '{50,68}'; -SELECT count(*) from test__int WHERE a @@ '(20&23)|(50&68)'; - -drop index text_idx; -CREATE INDEX text_idx on test__int using gist ( a gist__intbig_ops ); - -SELECT count(*) from test__int WHERE a && '{23,50}'; -SELECT count(*) from test__int WHERE a @@ '23|50'; -SELECT count(*) from test__int WHERE a @ '{23,50}'; -SELECT count(*) from test__int WHERE a @@ '23&50'; -SELECT count(*) from test__int WHERE a @ '{20,23}'; -SELECT count(*) from test__int WHERE a @@ '50&68'; -SELECT count(*) from test__int WHERE a @ '{20,23}' or a @ '{50,68}'; -SELECT count(*) from test__int WHERE a @@ '(20&23)|(50&68)'; - |