bloom-contrib.9.patch

application/octet-stream

Filename: bloom-contrib.9.patch
Type: application/octet-stream
Part: 2
Message: Re: WIP: Access method extendability

Patch

Format: unified
File+
contrib/bloom/blcost.c 0 0
contrib/bloom/blinsert.c 0 0
contrib/bloom/bloom--1.0.sql 0 0
contrib/bloom/bloom.control 0 0
contrib/bloom/bloom.h 0 0
contrib/bloom/blscan.c 0 0
contrib/bloom/blutils.c 0 0
contrib/bloom/blvacuum.c 0 0
contrib/bloom/blvalidate.c 0 0
contrib/bloom/data/data 0 0
contrib/bloom/expected/bloom.out 0 0
contrib/bloom/.gitignore 0 0
contrib/bloom/Makefile 0 0
contrib/bloom/sql/bloom.sql 0 0
contrib/bloom/t/001_wal.pl 0 0
contrib/Makefile 0 0
doc/src/sgml/bloom.sgml 0 0
doc/src/sgml/contrib.sgml 0 0
doc/src/sgml/filelist.sgml 0 0
diff --git a/contrib/Makefile b/contrib/Makefile
new file mode 100644
index bd251f6..3ac3818
*** a/contrib/Makefile
--- b/contrib/Makefile
*************** SUBDIRS = \
*** 8,13 ****
--- 8,14 ----
  		adminpack	\
  		auth_delay	\
  		auto_explain	\
+ 		bloom		\
  		btree_gin	\
  		btree_gist	\
  		chkpass		\
diff --git a/contrib/bloom/.gitignore b/contrib/bloom/.gitignore
new file mode 100644
index ...5dcb3ff
*** a/contrib/bloom/.gitignore
--- b/contrib/bloom/.gitignore
***************
*** 0 ****
--- 1,4 ----
+ # Generated subdirectories
+ /log/
+ /results/
+ /tmp_check/
diff --git a/contrib/bloom/Makefile b/contrib/bloom/Makefile
new file mode 100644
index ...13bd397
*** a/contrib/bloom/Makefile
--- b/contrib/bloom/Makefile
***************
*** 0 ****
--- 1,24 ----
+ # contrib/bloom/Makefile
+ 
+ MODULE_big = bloom
+ OBJS = blcost.o blinsert.o blscan.o blutils.o blvacuum.o blvalidate.o $(WIN32RES)
+ 
+ EXTENSION = bloom
+ DATA = bloom--1.0.sql
+ PGFILEDESC = "bloom access method - signature file based index"
+ 
+ REGRESS = bloom
+ 
+ ifdef USE_PGXS
+ PG_CONFIG = pg_config
+ PGXS := $(shell $(PG_CONFIG) --pgxs)
+ include $(PGXS)
+ else
+ subdir = contrib/bloom
+ top_builddir = ../..
+ include $(top_builddir)/src/Makefile.global
+ include $(top_srcdir)/contrib/contrib-global.mk
+ endif
+ 
+ wal-check: temp-install
+ 	$(prove_check)
diff --git a/contrib/bloom/blcost.c b/contrib/bloom/blcost.c
new file mode 100644
index ...d918dce
*** a/contrib/bloom/blcost.c
--- b/contrib/bloom/blcost.c
***************
*** 0 ****
--- 1,45 ----
+ /*-------------------------------------------------------------------------
+  *
+  * blcost.c
+  *		Cost estimate function for bloom indexes.
+  *
+  * Copyright (c) 2016, PostgreSQL Global Development Group
+  *
+  * IDENTIFICATION
+  *	  contrib/bloom/blcost.c
+  *
+  *-------------------------------------------------------------------------
+  */
+ #include "postgres.h"
+ 
+ #include "fmgr.h"
+ #include "optimizer/cost.h"
+ #include "utils/selfuncs.h"
+ 
+ #include "bloom.h"
+ 
+ void
+ blcostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
+ 			   Cost *indexStartupCost, Cost *indexTotalCost,
+ 			   Selectivity *indexSelectivity, double *indexCorrelation)
+ {
+ 	IndexOptInfo   *index = path->indexinfo;
+ 	List		   *qinfos;
+ 	GenericCosts	costs;
+ 
+ 	/* Do preliminary analysis of indexquals */
+ 	qinfos = deconstruct_indexquals(path);
+ 
+ 	MemSet(&costs, 0, sizeof(costs));
+ 
+ 	/* We have to visit all index tuples anyway */
+ 	costs.numIndexTuples = index->tuples;
+ 
+ 	/* Use generic estimate */
+ 	genericcostestimate(root, path, loop_count, qinfos, &costs);
+ 
+ 	*indexStartupCost = costs.indexStartupCost;
+ 	*indexTotalCost = costs.indexTotalCost;
+ 	*indexSelectivity = costs.indexSelectivity;
+ 	*indexCorrelation = costs.indexCorrelation;
+ }
diff --git a/contrib/bloom/blinsert.c b/contrib/bloom/blinsert.c
new file mode 100644
index ...15bff40
*** a/contrib/bloom/blinsert.c
--- b/contrib/bloom/blinsert.c
***************
*** 0 ****
--- 1,293 ----
+ /*-------------------------------------------------------------------------
+  *
+  * blinsert.c
+  *		Bloom index build and insert functions.
+  *
+  * Copyright (c) 2016, PostgreSQL Global Development Group
+  *
+  * IDENTIFICATION
+  *	  contrib/bloom/blinsert.c
+  *
+  *-------------------------------------------------------------------------
+  */
+ #include "postgres.h"
+ 
+ #include "access/genam.h"
+ #include "access/generic_xlog.h"
+ #include "catalog/index.h"
+ #include "miscadmin.h"
+ #include "storage/bufmgr.h"
+ #include "storage/indexfsm.h"
+ #include "utils/memutils.h"
+ #include "utils/rel.h"
+ 
+ #include "bloom.h"
+ 
+ PG_MODULE_MAGIC;
+ 
+ typedef struct
+ {
+ 	BloomState		blstate;
+ 	MemoryContext	tmpCtx;
+ 	char			data[BLCKSZ];
+ 	int64			count;
+ } BloomBuildState;
+ 
+ /*
+  * Flush page cached in BloomBuildState.
+  */
+ static void
+ flushCachedPage(Relation index, BloomBuildState *buildstate)
+ {
+ 	Page	page;
+ 	Buffer	buffer = BloomNewBuffer(index);
+ 
+ 	GenericXLogStart(index);
+ 	page = GenericXLogRegister(buffer, true);
+ 	memcpy(page, buildstate->data, BLCKSZ);
+ 	GenericXLogFinish();
+ 	UnlockReleaseBuffer(buffer);
+ }
+ 
+ /*
+  * (Re)initialize cached page in BloomBuildState.
+  */
+ static void
+ initCachedPage(BloomBuildState *buildstate)
+ {
+ 	memset(buildstate->data, 0, BLCKSZ);
+ 	BloomInitPage(buildstate->data, 0);
+ 	buildstate->count = 0;
+ }
+ 
+ /*
+  * Per-tuple callback from IndexBuildHeapScan.
+  */
+ static void
+ bloomBuildCallback(Relation index, HeapTuple htup, Datum *values,
+ 					bool *isnull, bool tupleIsAlive, void *state)
+ {
+ 	BloomBuildState	*buildstate = (BloomBuildState *)state;
+ 	MemoryContext	 oldCtx;
+ 	BloomTuple		*itup;
+ 
+ 	oldCtx = MemoryContextSwitchTo(buildstate->tmpCtx);
+ 
+ 	itup = BloomFormTuple(&buildstate->blstate, &htup->t_self, values, isnull);
+ 
+ 	/* Try to add next item to cached page */
+ 	if (BloomPageAddItem(&buildstate->blstate, buildstate->data, itup) == false)
+ 	{
+ 		/* Cached page is full, flush it out and make a new one */
+ 		flushCachedPage(index, buildstate);
+ 
+ 		CHECK_FOR_INTERRUPTS();
+ 
+ 		initCachedPage(buildstate);
+ 
+ 		if (BloomPageAddItem(&buildstate->blstate, buildstate->data, itup) == false)
+ 		{
+ 			/* We shouldn't be here since we're inserting to the empty page */
+ 			elog(ERROR, "can not add new tuple");
+ 		}
+ 	}
+ 	else
+ 	{
+ 		buildstate->count++;
+ 	}
+ 
+ 	MemoryContextSwitchTo(oldCtx);
+ 	MemoryContextReset(buildstate->tmpCtx);
+ }
+ 
+ IndexBuildResult *
+ blbuild(Relation heap, Relation index, IndexInfo *indexInfo)
+ {
+ 	IndexBuildResult   *result;
+ 	double				reltuples;
+ 	BloomBuildState		buildstate;
+ 
+ 	if (RelationGetNumberOfBlocks(index) != 0)
+ 		elog(ERROR, "index \"%s\" already contains data",
+ 			RelationGetRelationName(index));
+ 
+ 	/* Initialize the meta page */
+ 	BloomInitMetapage(index);
+ 
+ 	initBloomState(&buildstate.blstate, index);
+ 
+ 	buildstate.tmpCtx = AllocSetContextCreate(CurrentMemoryContext,
+ 												"Bloom build temporary context",
+ 												ALLOCSET_DEFAULT_MINSIZE,
+ 												ALLOCSET_DEFAULT_INITSIZE,
+ 												ALLOCSET_DEFAULT_MAXSIZE);
+ 
+ 	initCachedPage(&buildstate);
+ 
+ 	/* Do the heap scan */
+ 	reltuples = IndexBuildHeapScan(heap, index, indexInfo, true,
+ 									bloomBuildCallback, (void *) &buildstate);
+ 
+ 	if (buildstate.count > 0)
+ 		flushCachedPage(index, &buildstate);
+ 
+ 	MemoryContextDelete(buildstate.tmpCtx);
+ 
+ 	result = (IndexBuildResult *) palloc(sizeof(IndexBuildResult));
+ 	result->heap_tuples = result->index_tuples = reltuples;
+ 
+ 	return result;
+ }
+ 
+ void
+ blbuildempty(Relation index)
+ {
+ 	if (RelationGetNumberOfBlocks(index) != 0)
+ 		elog(ERROR, "index \"%s\" already contains data",
+ 			RelationGetRelationName(index));
+ 
+ 	/* Initialize the meta page */
+ 	BloomInitMetapage(index);
+ }
+ 
+ bool
+ blinsert(Relation index, Datum *values, bool *isnull,
+ 		ItemPointer ht_ctid, Relation heapRel, IndexUniqueCheck checkUnique)
+ {
+ 	BloomState			blstate;
+ 	BloomTuple		   *itup;
+ 	MemoryContext		oldCtx;
+ 	MemoryContext		insertCtx;
+ 	BloomMetaPageData  *metaData;
+ 	Buffer				buffer,
+ 						metaBuffer;
+ 	Page				page,
+ 						metaPage;
+ 	BlockNumber			blkno = InvalidBlockNumber;
+ 	OffsetNumber		nStart;
+ 
+ 	insertCtx = AllocSetContextCreate(CurrentMemoryContext,
+ 										"Bloom insert temporary context",
+ 										ALLOCSET_DEFAULT_MINSIZE,
+ 										ALLOCSET_DEFAULT_INITSIZE,
+ 										ALLOCSET_DEFAULT_MAXSIZE);
+ 
+ 	oldCtx = MemoryContextSwitchTo(insertCtx);
+ 
+ 	initBloomState(&blstate, index);
+ 	itup = BloomFormTuple(&blstate, ht_ctid, values, isnull);
+ 
+ 	/*
+ 	 * At first, try to insert new tuple to the first page in
+ 	 * notFullPage array.  If success we don't need to modify the
+ 	 * meta page.
+ 	 */
+ 	metaBuffer = ReadBuffer(index, BLOOM_METAPAGE_BLKNO);
+ 	LockBuffer(metaBuffer, BUFFER_LOCK_SHARE);
+ 	metaData = BloomPageGetMeta(BufferGetPage(metaBuffer));
+ 
+ 	if (metaData->nEnd > metaData->nStart)
+ 	{
+ 		Page	page;
+ 
+ 		blkno = metaData->notFullPage[metaData->nStart];
+ 
+ 		Assert(blkno != InvalidBlockNumber);
+ 		LockBuffer(metaBuffer, BUFFER_LOCK_UNLOCK);
+ 
+ 		buffer = ReadBuffer(index, blkno);
+ 		LockBuffer(buffer, BUFFER_LOCK_EXCLUSIVE);
+ 		GenericXLogStart(index);
+ 		page = GenericXLogRegister(buffer, false);
+ 
+ 		if (BloomPageAddItem(&blstate, page, itup))
+ 		{
+ 			GenericXLogFinish();
+ 			UnlockReleaseBuffer(buffer);
+ 			ReleaseBuffer(metaBuffer);
+ 			goto away;
+ 		}
+ 		else
+ 		{
+ 			GenericXLogAbort();
+ 			UnlockReleaseBuffer(buffer);
+ 		}
+ 	}
+ 	else
+ 	{
+ 		/* First page in notFullPage isn't suitable */
+ 		LockBuffer(metaBuffer, BUFFER_LOCK_UNLOCK);
+ 	}
+ 
+ 	/*
+ 	 * Try other pages in notFullPage array.  We will have to change nStart
+ 	 * in metapage.  Thus, grab exclusive lock on metapage.
+ 	 */
+ 	LockBuffer(metaBuffer, BUFFER_LOCK_EXCLUSIVE);
+ 
+ 	GenericXLogStart(index);
+ 	metaPage = GenericXLogRegister(metaBuffer, false);
+ 	metaData = BloomPageGetMeta(metaPage);
+ 
+ 	/*
+ 	 * Iterate over notFullPage array.  Skip page we already tried first.
+ 	 */
+ 	nStart = metaData->nStart;
+ 	if (metaData->nEnd > nStart &&
+ 		blkno == metaData->notFullPage[nStart] )
+ 		nStart++;
+ 
+ 	while (metaData->nEnd > nStart)
+ 	{
+ 		blkno = metaData->notFullPage[nStart];
+ 		Assert(blkno != InvalidBlockNumber);
+ 
+ 		buffer = ReadBuffer(index, blkno);
+ 		LockBuffer(buffer, BUFFER_LOCK_EXCLUSIVE);
+ 		page = GenericXLogRegister(buffer, false);
+ 
+ 		if (BloomPageAddItem(&blstate, page, itup))
+ 		{
+ 			metaData->nStart = nStart;
+ 			GenericXLogFinish();
+ 			UnlockReleaseBuffer(buffer);
+ 			UnlockReleaseBuffer(metaBuffer);
+ 			goto away;
+ 		}
+ 		else
+ 		{
+ 			GenericXLogUnregister(buffer);
+ 			UnlockReleaseBuffer(buffer);
+ 		}
+ 		nStart++;
+ 	}
+ 
+ 	GenericXLogAbort();
+ 
+ 	/*
+ 	 * Didn't find place to insert in notFullPage array.  Allocate new page.
+ 	 */
+ 	buffer = BloomNewBuffer(index);
+ 
+ 	GenericXLogStart(index);
+ 	metaPage = GenericXLogRegister(metaBuffer, false);
+ 	metaData = BloomPageGetMeta(metaPage);
+ 	page = GenericXLogRegister(buffer, true);
+ 	BloomInitPage(page, 0);
+ 	BloomPageAddItem(&blstate, page, itup);
+ 
+ 	metaData->nStart = 0;
+ 	metaData->nEnd = 1;
+ 	metaData->notFullPage[ 0 ] = BufferGetBlockNumber(buffer);
+ 
+ 	GenericXLogFinish();
+ 
+ 	UnlockReleaseBuffer(buffer);
+ 	UnlockReleaseBuffer(metaBuffer);
+ 
+ away:
+ 	MemoryContextSwitchTo(oldCtx);
+ 	MemoryContextDelete(insertCtx);
+ 
+ 	return false;
+ }
diff --git a/contrib/bloom/bloom--1.0.sql b/contrib/bloom/bloom--1.0.sql
new file mode 100644
index ...7fa7513
*** a/contrib/bloom/bloom--1.0.sql
--- b/contrib/bloom/bloom--1.0.sql
***************
*** 0 ****
--- 1,19 ----
+ CREATE OR REPLACE FUNCTION blhandler(internal)
+ RETURNS index_am_handler
+ AS 'MODULE_PATHNAME'
+ LANGUAGE C;
+ 
+ -- Access method
+ CREATE ACCESS METHOD bloom TYPE INDEX HANDLER blhandler;
+ 
+ -- Opclasses
+ 
+ CREATE OPERATOR CLASS int4_ops
+ DEFAULT FOR TYPE int4 USING bloom AS
+ 	OPERATOR	1	=(int4, int4),
+ 	FUNCTION	1	hashint4(int4);
+ 
+ CREATE OPERATOR CLASS text_ops
+ DEFAULT FOR TYPE text USING bloom AS
+ 	OPERATOR	1	=(text, text),
+ 	FUNCTION	1	hashtext(text);
diff --git a/contrib/bloom/bloom.control b/contrib/bloom/bloom.control
new file mode 100644
index ...4d4124b
*** a/contrib/bloom/bloom.control
--- b/contrib/bloom/bloom.control
***************
*** 0 ****
--- 1,5 ----
+ # bloom extension
+ comment = 'bloom access method - signature file based index'
+ default_version = '1.0'
+ module_pathname = '$libdir/bloom'
+ relocatable = true
diff --git a/contrib/bloom/bloom.h b/contrib/bloom/bloom.h
new file mode 100644
index ...6f20ee4
*** a/contrib/bloom/bloom.h
--- b/contrib/bloom/bloom.h
***************
*** 0 ****
--- 1,176 ----
+ /*-------------------------------------------------------------------------
+  *
+  * bloom.h
+  *	  Header for bloom index.
+  *
+  * Copyright (c) 2016, PostgreSQL Global Development Group
+  *
+  * IDENTIFICATION
+  *	  contrib/bloom/bloom.h
+  *
+  *-------------------------------------------------------------------------
+  */
+ #ifndef _BLOOM_H_
+ #define _BLOOM_H_
+ 
+ #include "access/amapi.h"
+ #include "access/generic_xlog.h"
+ #include "access/itup.h"
+ #include "access/xlog.h"
+ #include "nodes/relation.h"
+ #include "fmgr.h"
+ 
+ /* Support procedures numbers */
+ #define	BLOOM_HASH_PROC			1
+ #define	BLOOM_NPROC				1
+ 
+ /* Scan strategies */
+ #define	BLOOM_EQUAL_STRATEGY	1
+ #define	BLOOM_NSTRATEGIES		1
+ 
+ /* Opaque for bloom pages */
+ typedef struct BloomPageOpaqueData
+ {
+ 	OffsetNumber	maxoff;
+ 	uint16			flags;
+ } BloomPageOpaqueData;
+ 
+ typedef BloomPageOpaqueData *BloomPageOpaque;
+ 
+ /* Bloom page flags */
+ #define BLOOM_META		(1<<0)
+ #define BLOOM_DELETED	(2<<0)
+ 
+ #define BloomPageGetOpaque(page) ((BloomPageOpaque) PageGetSpecialPointer(page))
+ #define BloomPageGetMaxOffset(page) (BloomPageGetOpaque(page)->maxoff)
+ #define BloomPageIsMeta(page) (BloomPageGetOpaque(page)->flags & BLOOM_META)
+ #define BloomPageIsDeleted(page) (BloomPageGetOpaque(page)->flags & BLOOM_DELETED)
+ #define BloomPageSetDeleted(page) (BloomPageGetOpaque(page)->flags |= BLOOM_DELETED)
+ #define BloomPageSetNonDeleted(page) (BloomPageGetOpaque(page)->flags &= ~BLOOM_DELETED)
+ #define BloomPageGetData(page)		((BloomTuple *)PageGetContents(page))
+ #define BloomPageGetTuple(state, page, offset) \
+ 	((BloomTuple *)(PageGetContents(page) \
+ 		+ (state)->sizeOfBloomTuple * ((offset) - 1)))
+ #define BloomPageGetNextTuple(state, tuple) \
+ 	((BloomTuple *)((Pointer)(tuple) + (state)->sizeOfBloomTuple))
+ 
+ /* Preserved page numbers */
+ #define BLOOM_METAPAGE_BLKNO	(0)
+ #define BLOOM_HEAD_BLKNO		(1) /* first data page */
+ 
+ /* Bloom index options */
+ typedef struct BloomOptions
+ {
+ 	int32	vl_len_;				 /* varlena header (do not touch directly!) */
+ 	int		bloomLength;			 /* length of signature in uint16 */
+ 	int		bitSize[INDEX_MAX_KEYS]; /* signature bits per index key */
+ } BloomOptions;
+ 
+ /*
+  * FreeBlockNumberArray - array of block numbers sized so that metadata fill
+  * all space in metapage.
+  */
+ typedef BlockNumber FreeBlockNumberArray[
+ 	MAXALIGN_DOWN(
+ 		BLCKSZ - SizeOfPageHeaderData - MAXALIGN(sizeof(BloomPageOpaqueData))
+ 			   - MAXALIGN(sizeof(uint16) * 2 + sizeof(uint32) + sizeof(BloomOptions))
+ 	) / sizeof(BlockNumber) 
+ ];
+ 
+ /* Metadata of bloom index */
+ typedef struct BloomMetaPageData
+ {
+ 	uint32					magickNumber;
+ 	uint16					nStart;
+ 	uint16					nEnd;
+ 	BloomOptions			opts;
+ 	FreeBlockNumberArray	notFullPage;
+ } BloomMetaPageData;
+ 
+ /* Magic number to distinguish bloom pages among anothers */
+ #define BLOOM_MAGICK_NUMBER	(0xDBAC0DED)
+ 
+ /* Number of blocks numbers fit in BloomMetaPageData */
+ #define BloomMetaBlockN		(sizeof(FreeBlockNumberArray) / sizeof(BlockNumber))
+ 
+ #define BloomPageGetMeta(page)	((BloomMetaPageData *) PageGetContents(page))
+ 
+ typedef struct BloomState 
+ {
+ 	FmgrInfo			hashFn[INDEX_MAX_KEYS];
+ 	BloomOptions	   *opts; /* stored in rd_amcache and defined at creation time */
+ 	int32				nColumns;
+ 	/* 
+ 	 * sizeOfBloomTuple is index's specific, and it depends on
+ 	 * reloptions, so precompute it
+ 	 */
+ 	int32				sizeOfBloomTuple; 
+ } BloomState;
+ 
+ #define BloomPageGetFreeSpace(state, page) \
+ 	(BLCKSZ - MAXALIGN(SizeOfPageHeaderData) \
+ 		- BloomPageGetMaxOffset(page) * (state)->sizeOfBloomTuple \
+ 		- MAXALIGN(sizeof(BloomPageOpaqueData)))
+ 
+ /*
+  * Tuples are very different from all other relations
+  */
+ typedef uint16	SignType;
+ 
+ typedef struct BloomTuple
+ {
+ 	ItemPointerData		heapPtr;
+ 	SignType			sign[1];
+ } BloomTuple;
+ 
+ #define BLOOMTUPLEHDRSZ	offsetof(BloomTuple, sign)
+ 
+ /* Opaque data structure for bloom index scan */
+ typedef struct BloomScanOpaqueData
+ {
+ 	SignType   *sign;	/* Scan signature */
+ 	BloomState	state;
+ } BloomScanOpaqueData;
+ 
+ typedef BloomScanOpaqueData *BloomScanOpaque;
+ 
+ /* blutils.c */
+ extern void _PG_init(void);
+ extern Datum blhandler(PG_FUNCTION_ARGS);
+ extern void initBloomState(BloomState *state, Relation index);
+ extern void BloomInitMetapage(Relation index);
+ extern void BloomInitPage(Page page, uint16 flags);
+ extern Buffer BloomNewBuffer(Relation index);
+ extern void signValue(BloomState *state, SignType *sign, Datum value, int attno);
+ extern BloomTuple* BloomFormTuple(BloomState *state, ItemPointer iptr, Datum *values, bool *isnull);
+ extern bool BloomPageAddItem(BloomState *state, Page page, BloomTuple *tuple);
+ 
+ /* blvalidate.c */
+ extern bool blvalidate(Oid opclassoid);
+ 
+ /* interface functions */
+ extern bool blinsert(Relation index, Datum *values, bool *isnull,
+ 					 ItemPointer ht_ctid, Relation heapRel,
+ 					 IndexUniqueCheck checkUnique);
+ extern IndexScanDesc blbeginscan(Relation r, int nkeys, int norderbys);
+ extern int64 blgetbitmap(IndexScanDesc scan, TIDBitmap *tbm);
+ extern void blrescan(IndexScanDesc scan, ScanKey scankey, int nscankeys,
+ 					 ScanKey orderbys, int norderbys);
+ extern void blendscan(IndexScanDesc scan);
+ extern void blmarkpos(IndexScanDesc scan);
+ extern void blrestrpos(IndexScanDesc scan);
+ extern IndexBuildResult *blbuild(Relation heap, Relation index,
+ 								   struct IndexInfo *indexInfo);
+ extern void blbuildempty(Relation index);
+ extern IndexBulkDeleteResult *blbulkdelete(IndexVacuumInfo *info,
+ 	IndexBulkDeleteResult *stats, IndexBulkDeleteCallback callback,
+ 	void *callback_state);
+ extern IndexBulkDeleteResult *blvacuumcleanup(IndexVacuumInfo *info,
+ 	IndexBulkDeleteResult *stats);
+ extern bytea *bloptions(Datum reloptions, bool validate);
+ extern void blcostestimate(PlannerInfo *root, IndexPath *path,
+ 						   double loop_count, Cost *indexStartupCost,
+ 						   Cost *indexTotalCost, Selectivity *indexSelectivity,
+ 						   double *indexCorrelation);
+ 
+ #endif
diff --git a/contrib/bloom/blscan.c b/contrib/bloom/blscan.c
new file mode 100644
index ...467a1b1
*** a/contrib/bloom/blscan.c
--- b/contrib/bloom/blscan.c
***************
*** 0 ****
--- 1,174 ----
+ /*-------------------------------------------------------------------------
+  *
+  * blscan.c
+  *		Bloom index scan functions.
+  *
+  * Copyright (c) 2016, PostgreSQL Global Development Group
+  *
+  * IDENTIFICATION
+  *	  contrib/bloom/blscan.c
+  *
+  *-------------------------------------------------------------------------
+  */
+ #include "postgres.h"
+ 
+ #include "access/relscan.h"
+ #include "pgstat.h"
+ #include "miscadmin.h"
+ #include "storage/bufmgr.h"
+ #include "storage/lmgr.h"
+ #include "utils/memutils.h"
+ #include "utils/rel.h"
+ 
+ #include "bloom.h"
+ 
+ IndexScanDesc
+ blbeginscan(Relation r, int nkeys, int norderbys)
+ {
+ 	IndexScanDesc scan;
+ 
+ 	scan = RelationGetIndexScan(r, nkeys, norderbys);
+ 
+ 	return scan;
+ }
+ 
+ void
+ blrescan(IndexScanDesc scan, ScanKey scankey, int nscankeys,
+ 							 ScanKey orderbys, int norderbys)
+ {
+ 	BloomScanOpaque so;
+ 
+ 	so = (BloomScanOpaque) scan->opaque;
+ 
+ 	if (so == NULL)
+ 	{
+ 		/* if called from blbeginscan */
+ 		so = (BloomScanOpaque) palloc(sizeof(BloomScanOpaqueData));
+ 		initBloomState(&so->state, scan->indexRelation);
+ 		scan->opaque = so;
+ 
+ 	}
+ 	else
+ 	{
+ 		if (so->sign)
+ 			pfree(so->sign);
+ 	}
+ 	so->sign = NULL;
+ 
+ 	if (scankey && scan->numberOfKeys > 0)
+ 	{
+ 		memmove(scan->keyData, scankey,
+ 				scan->numberOfKeys * sizeof(ScanKeyData));
+ 	}
+ }
+ 
+ void
+ blendscan(IndexScanDesc scan)
+ {
+ 	BloomScanOpaque so = (BloomScanOpaque) scan->opaque;
+ 
+ 	if (so->sign)
+ 		pfree(so->sign);
+ 	so->sign = NULL;
+ }
+ 
+ void
+ blmarkpos(IndexScanDesc scan)
+ {
+ 	elog(ERROR, "Bloom does not support mark/restore");
+ }
+ 
+ void
+ blrestrpos(IndexScanDesc scan)
+ {
+ 	elog(ERROR, "Bloom does not support mark/restore");
+ }
+ 
+ int64
+ blgetbitmap(IndexScanDesc scan, TIDBitmap *tbm)
+ {
+ 	int64					ntids = 0;
+ 	BlockNumber				blkno = BLOOM_HEAD_BLKNO,
+ 							npages;
+ 	int						i;
+ 	BufferAccessStrategy	bas;
+ 	BloomScanOpaque 		so = (BloomScanOpaque) scan->opaque;
+ 
+ 	if (so->sign == NULL && scan->numberOfKeys > 0)
+ 	{
+ 		/* New search: have to calculate search signature */
+ 		ScanKey skey = scan->keyData;
+ 
+ 		so->sign = palloc0(sizeof(SignType) * so->state.opts->bloomLength); 
+ 		
+ 		for(i = 0; i < scan->numberOfKeys; i++)
+ 		{
+ 			/*
+ 			 * Assume bloom-indexable operators to be strict, so nothing
+ 			 * could be found for NULL key.
+ 			 */
+ 			if (skey->sk_flags & SK_ISNULL)
+ 			{
+ 				pfree(so->sign);
+ 				so->sign = NULL;
+ 				return 0;
+ 			}
+ 
+ 			/* Add next value to the signature */
+ 			signValue(&so->state, so->sign, skey->sk_argument,
+ 					  skey->sk_attno - 1);
+ 
+ 			skey++;
+ 		}
+ 	}
+ 
+ 	/*
+ 	 * We're going to read the whole index. This is why we use appropriate
+ 	 * buffer access strategy.
+ 	 */
+ 	bas = GetAccessStrategy(BAS_BULKREAD);
+ 	npages = RelationGetNumberOfBlocks(scan->indexRelation);
+ 
+ 	for (blkno = BLOOM_HEAD_BLKNO; blkno < npages; blkno++)
+ 	{
+ 		Buffer 			buffer;
+ 		Page			page;
+ 
+ 		buffer = ReadBufferExtended(scan->indexRelation, MAIN_FORKNUM,
+ 									blkno, RBM_NORMAL, bas);
+ 
+ 		LockBuffer(buffer, BUFFER_LOCK_SHARE);
+ 		page = BufferGetPage(buffer);
+ 
+ 		if (!BloomPageIsDeleted(page))
+ 		{
+ 			OffsetNumber offset, maxOffset = BloomPageGetMaxOffset(page);
+ 
+ 			for (offset = 1; offset <= maxOffset; offset++)
+ 			{
+ 				BloomTuple *itup = BloomPageGetTuple(&so->state, page, offset);
+ 				bool		res = true;
+ 
+ 				/* Check index signature with scan signature */
+ 				for (i = 0; res && i < so->state.opts->bloomLength; i++)
+ 				{
+ 					if ((itup->sign[i] & so->sign[i]) != so->sign[i])
+ 						res = false;
+ 				}
+ 
+ 				/* Add matching tuples to bitmap */
+ 				if (res)
+ 				{
+ 					tbm_add_tuples(tbm, &itup->heapPtr, 1, true);
+ 					ntids++;
+ 				}
+ 			}
+ 		}
+ 
+ 		UnlockReleaseBuffer(buffer);
+ 		CHECK_FOR_INTERRUPTS();
+ 	}
+ 	FreeAccessStrategy(bas);
+ 
+ 	return ntids;
+ }
diff --git a/contrib/bloom/blutils.c b/contrib/bloom/blutils.c
new file mode 100644
index ...a7ec0c5
*** a/contrib/bloom/blutils.c
--- b/contrib/bloom/blutils.c
***************
*** 0 ****
--- 1,390 ----
+ /*-------------------------------------------------------------------------
+  *
+  * blutils.c
+  *		Bloom index utilities.
+  *
+  * Copyright (c) 2016, PostgreSQL Global Development Group
+  *
+  * IDENTIFICATION
+  *	  contrib/bloom/blutils.c
+  *
+  *-------------------------------------------------------------------------
+  */
+ #include "postgres.h"
+ 
+ #include "access/amapi.h"
+ #include "access/generic_xlog.h"
+ #include "catalog/index.h"
+ #include "storage/lmgr.h"
+ #include "miscadmin.h"
+ #include "storage/bufmgr.h"
+ #include "storage/indexfsm.h"
+ #include "utils/memutils.h"
+ #include "access/reloptions.h"
+ #include "storage/freespace.h"
+ #include "storage/indexfsm.h"
+ 
+ #include "bloom.h"
+ 
+ /* Signature dealing macros */
+ #define BITSIGNTYPE	(BITS_PER_BYTE * sizeof(SignType))
+ #define GETWORD(x,i) ( *( (SignType*)(x) + (int)( (i) / BITSIGNTYPE ) ) )
+ #define CLRBIT(x,i)   GETWORD(x,i) &= ~( 0x01 << ( (i) % BITSIGNTYPE ) )
+ #define SETBIT(x,i)   GETWORD(x,i) |=  ( 0x01 << ( (i) % BITSIGNTYPE ) )
+ #define GETBIT(x,i) ( (GETWORD(x,i) >> ( (i) % BITSIGNTYPE )) & 0x01 )
+ 
+ PG_FUNCTION_INFO_V1(blhandler);
+ 
+ static relopt_kind bl_relopt_kind;
+ 
+ /*
+  * Module initialize function: initilized relation options.
+  */
+ void 
+ _PG_init(void)
+ {
+ 	int		i;
+ 	char	buf[16];
+ 
+ 	bl_relopt_kind = add_reloption_kind();
+ 
+ 	add_int_reloption(bl_relopt_kind, "length",
+ 					  "Length of signature in uint16 type", 5, 1, 256);
+ 
+ 	for(i = 0; i < INDEX_MAX_KEYS;i ++)
+ 	{
+ 		snprintf(buf, 16, "col%d", i+1);
+ 		add_int_reloption(bl_relopt_kind, buf,
+ 						  "Number of bits for corresponding column", 2, 1, 2048);
+ 	}
+ }
+ 
+ /*
+  * Bloom handler function: return IndexAmRoutine with access method parameters
+  * and callbacks.
+  */
+ Datum
+ blhandler(PG_FUNCTION_ARGS)
+ {
+ 	IndexAmRoutine *amroutine = makeNode(IndexAmRoutine);
+ 
+ 	amroutine->amstrategies = 1;
+ 	amroutine->amsupport = 1;
+ 	amroutine->amcanorder = false;
+ 	amroutine->amcanorderbyop = false;
+ 	amroutine->amcanbackward = false;
+ 	amroutine->amcanunique = false;
+ 	amroutine->amcanmulticol = true;
+ 	amroutine->amoptionalkey = true;
+ 	amroutine->amsearcharray = false;
+ 	amroutine->amsearchnulls = false;
+ 	amroutine->amstorage = false;
+ 	amroutine->amclusterable = false;
+ 	amroutine->ampredlocks = false;
+ 	amroutine->amkeytype = 0;
+ 
+ 	amroutine->aminsert = blinsert;
+ 	amroutine->ambeginscan = blbeginscan;
+ 	amroutine->amgettuple = NULL;
+ 	amroutine->amgetbitmap = blgetbitmap;
+ 	amroutine->amrescan = blrescan;
+ 	amroutine->amendscan = blendscan;
+ 	amroutine->ammarkpos = blmarkpos;
+ 	amroutine->amrestrpos = blrestrpos;
+ 	amroutine->ambuild = blbuild;
+ 	amroutine->ambuildempty = blbuildempty;
+ 	amroutine->ambulkdelete = blbulkdelete;
+ 	amroutine->amvacuumcleanup = blvacuumcleanup;
+ 	amroutine->amcanreturn = NULL;
+ 	amroutine->amcostestimate = blcostestimate;
+ 	amroutine->amoptions = bloptions;
+ 	amroutine->amvalidate = blvalidate;
+ 
+ 	PG_RETURN_POINTER(amroutine);
+ }
+ 
+ void 
+ initBloomState(BloomState *state, Relation index)
+ {
+ 	int	i;
+ 
+ 	state->nColumns = index->rd_att->natts;
+ 
+ 	/* Initialize hash function for each attribute */
+ 	for (i = 0; i < index->rd_att->natts; i++)
+ 	{
+ 		fmgr_info_copy(&(state->hashFn[i]),
+ 						index_getprocinfo(index, i + 1, BLOOM_HASH_PROC),
+ 						CurrentMemoryContext);
+ 	}
+ 
+ 	/* Inititalize amcache if needed */
+ 	if (!index->rd_amcache)
+ 	{
+ 		Buffer				buffer;
+ 		Page				page;
+ 		BloomMetaPageData	*meta;
+ 		BloomOptions		*opts;
+ 
+ 		opts = MemoryContextAlloc(index->rd_indexcxt, sizeof(BloomOptions));
+ 
+ 		buffer = ReadBuffer(index, BLOOM_METAPAGE_BLKNO);
+ 		LockBuffer(buffer, BUFFER_LOCK_SHARE);
+ 
+ 		page = BufferGetPage(buffer);
+ 
+ 		if (!BloomPageIsMeta(page))
+ 			elog(ERROR, "Relation is not a bloom index");
+ 		meta = BloomPageGetMeta(BufferGetPage(buffer));
+ 
+ 		if (meta->magickNumber != BLOOM_MAGICK_NUMBER)
+ 			elog(ERROR, "Relation is not a bloom index");
+ 
+ 		*opts = meta->opts;
+ 
+ 		UnlockReleaseBuffer(buffer);
+ 
+ 		index->rd_amcache = (void *)opts;
+ 	}
+ 
+ 	state->opts = (BloomOptions *)index->rd_amcache;
+ 	state->sizeOfBloomTuple = BLOOMTUPLEHDRSZ +
+ 									sizeof(SignType) * state->opts->bloomLength; 
+ }
+ 
+ /*
+  * Add bits of given value to the signature.
+  */
+ void
+ signValue(BloomState *state, SignType *sign, Datum value, int attno)
+ {
+ 	uint32		hashVal;
+ 	int 		nBit, j;
+ 
+ 	/*
+ 	 * init generator with "column's" number to get
+ 	 * "hashed" seed for new value. We don't want to map
+ 	 * the same numbers from different columns into the same bits!
+ 	 */
+ 	srand(attno);
+ 
+ 	/*
+ 	 * Init hash sequence to map our value into bits. the same values
+ 	 * in different columns will be mapped into different bits because
+ 	 * of step above
+ 	 */
+ 	hashVal = DatumGetInt32(FunctionCall1(&state->hashFn[attno], value));
+ 	srand(hashVal ^ rand());
+ 
+ 	for (j = 0; j < state->opts->bitSize[attno]; j++)
+ 	{
+ 		/* prevent mutiple evaluation */
+ 		nBit = rand() % (state->opts->bloomLength * BITSIGNTYPE); 
+ 		SETBIT(sign, nBit);
+ 	}
+ }
+ 
+ /*
+  * Make bloom tuple from values.
+  */
+ BloomTuple *
+ BloomFormTuple(BloomState *state, ItemPointer iptr, Datum *values, bool *isnull)
+ {
+ 	int 		i;
+ 	BloomTuple *res = (BloomTuple *)palloc0(state->sizeOfBloomTuple);
+ 
+ 	res->heapPtr = *iptr;
+ 
+     /*
+ 	 * Blooming
+ 	 */
+ 	for (i = 0; i < state->nColumns; i++)
+ 	{
+ 		/* skip nulls */
+ 		if (isnull[i])
+ 			continue;
+ 
+ 		signValue(state, res->sign, values[i], i);
+ 	}
+ 
+ 	return res;
+ }
+ 
+ /*
+  * Add new bloom tuple to the page.
+  */
+ bool
+ BloomPageAddItem(BloomState *state, Page page, BloomTuple *tuple)
+ {
+ 	BloomTuple		   *itup;
+ 	BloomPageOpaque		opaque;
+ 	Pointer				ptr;
+ 
+ 	if (BloomPageGetFreeSpace(state, page) < state->sizeOfBloomTuple)
+ 		return false;
+ 
+ 	/* Copy new tuple to the end of page */
+ 	opaque = BloomPageGetOpaque(page);
+ 	itup = BloomPageGetTuple(state, page, opaque->maxoff + 1);
+ 	memcpy((Pointer)itup, (Pointer)tuple, state->sizeOfBloomTuple);
+ 
+ 	/* Adjust maxoff and pd_lower */
+ 	opaque->maxoff++;
+ 	ptr = (Pointer)BloomPageGetTuple(state, page, opaque->maxoff + 1);
+ 	((PageHeader) page)->pd_lower = ptr - page;
+ 
+ 	return true;
+ }
+ 
+ /*
+  * Allocate a new page (either by recycling, or by extending the index file)
+  * The returned buffer is already pinned and exclusive-locked
+  * Caller is responsible for initializing the page by calling BloomInitBuffer
+  */
+ Buffer
+ BloomNewBuffer(Relation index)
+ {
+ 	Buffer      buffer;
+ 	bool        needLock;
+ 
+ 	/* First, try to get a page from FSM */
+ 	for (;;)
+ 	{
+ 		BlockNumber blkno = GetFreeIndexPage(index);
+ 
+ 		if (blkno == InvalidBlockNumber)
+ 			break;
+ 
+ 		buffer = ReadBuffer(index, blkno);
+ 
+ 		/*
+ 		 * We have to guard against the possibility that someone else already
+ 		 * recycled this page; the buffer may be locked if so.
+ 		 */
+ 		if (ConditionalLockBuffer(buffer))
+ 		{
+ 			Page	page = BufferGetPage(buffer);
+ 
+ 			if (PageIsNew(page))
+ 				return buffer;  /* OK to use, if never initialized */
+ 
+ 			if (BloomPageIsDeleted(page))
+ 				return buffer;  /* OK to use */
+ 
+ 			LockBuffer(buffer, BUFFER_LOCK_UNLOCK);
+ 		}
+ 
+ 		/* Can't use it, so release buffer and try again */
+ 		ReleaseBuffer(buffer);
+ 	}
+ 
+ 	/* Must extend the file */
+ 	needLock = !RELATION_IS_LOCAL(index);
+ 	if (needLock)
+ 		LockRelationForExtension(index, ExclusiveLock);
+ 
+ 	buffer = ReadBuffer(index, P_NEW);
+ 	LockBuffer(buffer, BUFFER_LOCK_EXCLUSIVE);
+ 
+ 	if (needLock)
+ 		UnlockRelationForExtension(index, ExclusiveLock);
+ 
+ 	return buffer;
+ }
+ 
+ /*
+  * Initialize bloom page.
+  */
+ void
+ BloomInitPage(Page page, uint16 flags)
+ {
+ 	BloomPageOpaque opaque;
+ 
+ 	PageInit(page, BLCKSZ, sizeof(BloomPageOpaqueData));
+ 
+ 	opaque = BloomPageGetOpaque(page);
+ 	memset(opaque, 0, sizeof(BloomPageOpaqueData));
+ 	opaque->maxoff = 0;
+ 	opaque->flags = flags;
+ }
+ 
+ static BloomOptions *
+ makeDefaultBloomOptions(BloomOptions *opts)
+ {
+ 	int i;
+ 
+ 	if (!opts)
+ 		opts = palloc0(sizeof(BloomOptions));
+ 
+ 	if (opts->bloomLength <= 0)
+ 		opts->bloomLength = 5;
+ 
+ 	for(i = 0; i < INDEX_MAX_KEYS; i++)
+ 		if (opts->bitSize[i] <= 0
+ 				|| opts->bitSize[i] >= opts->bloomLength * sizeof(SignType))
+ 			opts->bitSize[i] = 2;
+ 
+ 	return opts;
+ }
+ 
+ /*
+  * Initialize metapage for bloom index.
+  */
+ void
+ BloomInitMetapage(Relation index)
+ {
+ 	Page				metaPage;
+ 	Buffer				metaBuffer;
+ 	BloomMetaPageData  *metadata;
+ 
+ 	metaBuffer = BloomNewBuffer(index);
+ 	Assert(BufferGetBlockNumber(metaBuffer) == BLOOM_METAPAGE_BLKNO);
+ 
+ 	GenericXLogStart(index);
+ 	metaPage = GenericXLogRegister(metaBuffer, true);
+ 
+ 	BloomInitPage(metaPage, BLOOM_META);
+ 	metadata = BloomPageGetMeta(metaPage);
+ 	memset(metadata, 0, sizeof(BloomMetaPageData));
+ 	metadata->magickNumber = BLOOM_MAGICK_NUMBER;
+ 	metadata->opts = *makeDefaultBloomOptions((BloomOptions*)index->rd_options);
+ 	((PageHeader) metaPage)->pd_lower += sizeof(BloomMetaPageData);
+ 
+ 	GenericXLogFinish();
+ 	UnlockReleaseBuffer(metaBuffer);
+ }
+ 
+ /*
+  * Initialize options for bloom index.
+  */
+ bytea *
+ bloptions(Datum reloptions, bool validate)
+ {
+ 	relopt_value	   *options;
+ 	int					numoptions;
+ 	BloomOptions	   *rdopts;
+ 	relopt_parse_elt	tab[INDEX_MAX_KEYS + 1];
+ 	int					i;
+ 	char				buf[16];
+ 
+ 	tab[0].optname = "length";
+ 	tab[0].opttype = RELOPT_TYPE_INT;
+ 	tab[0].offset = offsetof(BloomOptions, bloomLength);
+ 
+ 	for(i = 0; i < INDEX_MAX_KEYS; i++)
+ 	{
+ 		snprintf(buf, sizeof(buf), "col%d", i + 1);
+ 		tab[i + 1].optname = pstrdup(buf);
+ 		tab[i + 1].opttype = RELOPT_TYPE_INT;
+ 		tab[i + 1].offset = offsetof(BloomOptions, bitSize[i]);
+ 	}
+ 
+ 	options = parseRelOptions(reloptions, validate, bl_relopt_kind, &numoptions);
+ 	rdopts = allocateReloptStruct(sizeof(BloomOptions), options, numoptions);
+ 	fillRelOptions((void *) rdopts, sizeof(BloomOptions), options, numoptions,
+ 						validate, tab, INDEX_MAX_KEYS + 1);
+ 		
+ 	rdopts = makeDefaultBloomOptions(rdopts);
+ 
+ 	return (bytea *)rdopts;
+ }
diff --git a/contrib/bloom/blvacuum.c b/contrib/bloom/blvacuum.c
new file mode 100644
index ...c694714
*** a/contrib/bloom/blvacuum.c
--- b/contrib/bloom/blvacuum.c
***************
*** 0 ****
--- 1,195 ----
+ /*-------------------------------------------------------------------------
+  *
+  * blvacuum.c
+  *		Bloom VACUUM functions.
+  *
+  * Copyright (c) 2016, PostgreSQL Global Development Group
+  *
+  * IDENTIFICATION
+  *	  contrib/bloom/blvacuum.c
+  *
+  *-------------------------------------------------------------------------
+  */
+ #include "postgres.h"
+ 
+ #include "access/genam.h"
+ #include "catalog/storage.h"
+ #include "commands/vacuum.h"
+ #include "miscadmin.h"
+ #include "postmaster/autovacuum.h"
+ #include "storage/bufmgr.h"
+ #include "storage/indexfsm.h"
+ #include "storage/lmgr.h"
+ 
+ #include "bloom.h"
+ 
+ IndexBulkDeleteResult *
+ blbulkdelete(IndexVacuumInfo *info, IndexBulkDeleteResult *stats,
+ 			 IndexBulkDeleteCallback callback, void *callback_state)
+ {
+ 	Relation				index = info->index;
+ 	BlockNumber				blkno,
+ 							npages;
+ 	FreeBlockNumberArray	notFullPage;
+ 	int						countPage = 0;
+ 	BloomState				state;
+ 	Buffer					buffer;
+ 	Page					page;
+ 
+ 	if (stats == NULL)
+ 		stats = (IndexBulkDeleteResult *) palloc0(sizeof(IndexBulkDeleteResult));
+ 
+ 	initBloomState(&state, index); 
+ 
+ 	/*
+ 	 * Interate over the pages. We don't care about concurrently added pages,
+ 	 * they can't contain tuples to delete.
+ 	 */
+ 	npages = RelationGetNumberOfBlocks(index);
+ 	for (blkno = BLOOM_HEAD_BLKNO; blkno < npages; blkno++)
+ 	{
+ 		BloomTuple *itup, *itupPtr, *itupEnd;
+ 
+ 		buffer = ReadBufferExtended(index, MAIN_FORKNUM, blkno,
+ 									RBM_NORMAL, info->strategy);
+ 
+ 		LockBuffer(buffer, BUFFER_LOCK_EXCLUSIVE);
+ 		GenericXLogStart(index);
+ 		page = GenericXLogRegister(buffer, false);
+ 
+ 		if (BloomPageIsDeleted(page))
+ 		{
+ 			UnlockReleaseBuffer(buffer);
+ 			CHECK_FOR_INTERRUPTS();
+ 			continue;
+ 		}
+ 
+ 		/* Iterate over the tuples */
+ 		itup = BloomPageGetTuple(&state, page, 1);
+ 		itupPtr = BloomPageGetTuple(&state, page, 1);
+ 		itupEnd = BloomPageGetTuple(&state, page, BloomPageGetMaxOffset(page) + 1);
+ 		while (itup < itupEnd)
+ 		{
+ 			/* Do we have to delete this tuple? */
+ 			if (callback(&itup->heapPtr, callback_state))
+ 			{
+ 				stats->tuples_removed += 1;
+ 				BloomPageGetOpaque(page)->maxoff--;
+ 			} 
+ 			else 
+ 			{
+ 				if (itupPtr != itup)
+ 				{
+ 					/*
+ 					 * If we already delete something before, we have to move
+ 					 * this tuple backward.
+ 					 */
+ 					memmove((Pointer)itupPtr, (Pointer)itup,
+ 							state.sizeOfBloomTuple);
+ 				}
+ 				stats->num_index_tuples++;
+ 				itupPtr = BloomPageGetNextTuple(&state, itupPtr);
+ 			}
+ 
+ 			itup = BloomPageGetNextTuple(&state, itup);
+ 		}
+ 
+ 		/* Did we delete something? */
+ 		if (itupPtr != itup)
+ 		{
+ 			/* Is it empty page now? */
+ 			if (itupPtr == BloomPageGetData(page))
+ 				BloomPageSetDeleted(page);
+ 			/* Adjust pg_lower */
+ 			((PageHeader) page)->pd_lower = (Pointer)itupPtr - page;
+ 			/* Finish WAL-logging */
+ 			GenericXLogFinish();
+ 		}
+ 		else
+ 		{
+ 			/* Didn't change anything: abort WAL-logging */
+ 			GenericXLogAbort();
+ 		}
+ 
+ 		if (!BloomPageIsDeleted(page) && 
+ 				BloomPageGetFreeSpace(&state, page) > state.sizeOfBloomTuple && 
+ 				countPage < BloomMetaBlockN)
+ 			notFullPage[countPage++] = blkno;
+ 		UnlockReleaseBuffer(buffer);
+ 		CHECK_FOR_INTERRUPTS();
+ 	}
+ 
+ 	if (countPage > 0)
+ 	{
+ 		BloomMetaPageData	*metaData;
+ 
+ 		buffer = ReadBuffer(index, BLOOM_METAPAGE_BLKNO);
+ 		LockBuffer(buffer, BUFFER_LOCK_EXCLUSIVE);
+ 
+ 		GenericXLogStart(index);
+ 		page = GenericXLogRegister(buffer, false);
+ 
+ 		metaData = BloomPageGetMeta(page);
+ 		memcpy(metaData->notFullPage, notFullPage, sizeof(FreeBlockNumberArray));
+ 		metaData->nStart=0;
+ 		metaData->nEnd = countPage;
+ 
+ 		GenericXLogFinish();
+ 		UnlockReleaseBuffer(buffer);
+ 	}
+ 
+ 	return stats;
+ }
+ 
+ IndexBulkDeleteResult *
+ blvacuumcleanup(IndexVacuumInfo *info, IndexBulkDeleteResult *stats)
+ {
+ 	Relation	index = info->index;
+ 	BlockNumber npages,
+ 				blkno;
+ 	BlockNumber	totFreePages;
+ 
+ 	if (info->analyze_only)
+ 		return stats;
+ 
+ 	if (stats == NULL)
+ 		stats = (IndexBulkDeleteResult *) palloc0(sizeof(IndexBulkDeleteResult));
+ 
+ 	/*
+ 	 * Iterate over the pages: insert deleted pages into FSM and collect
+ 	 * statistics.
+ 	 */
+ 	npages = RelationGetNumberOfBlocks(index);
+ 	totFreePages = 0;
+ 	for (blkno = BLOOM_HEAD_BLKNO; blkno < npages; blkno++)
+ 	{
+ 		Buffer		buffer;
+ 		Page		page;
+ 
+ 		vacuum_delay_point();
+ 
+ 		buffer = ReadBufferExtended(index, MAIN_FORKNUM, blkno,
+ 									RBM_NORMAL, info->strategy);
+ 		LockBuffer(buffer, BUFFER_LOCK_SHARE);
+ 		page = (Page) BufferGetPage(buffer);
+ 
+ 		if (BloomPageIsDeleted(page))
+ 		{
+ 			RecordFreeIndexPage(index, blkno);
+ 			totFreePages++;
+ 		}
+ 		else
+ 		{
+ 			stats->num_index_tuples += BloomPageGetMaxOffset(page);
+ 			stats->estimated_count += BloomPageGetMaxOffset(page);
+ 		}
+ 
+ 		UnlockReleaseBuffer(buffer);
+ 	}
+ 
+ 	IndexFreeSpaceMapVacuum(info->index);
+ 	stats->pages_free = totFreePages;
+ 	stats->num_pages = RelationGetNumberOfBlocks(index);
+ 
+ 	return stats;
+ }
diff --git a/contrib/bloom/blvalidate.c b/contrib/bloom/blvalidate.c
new file mode 100644
index ...5344b81
*** a/contrib/bloom/blvalidate.c
--- b/contrib/bloom/blvalidate.c
***************
*** 0 ****
--- 1,220 ----
+ /*-------------------------------------------------------------------------
+  *
+  * blvalidate.c
+  *	  Opclass validator for bloom.
+  *
+  * Copyright (c) 2016, PostgreSQL Global Development Group
+  *
+  * IDENTIFICATION
+  *	  contrib/bloom/blvalidate.c
+  *
+  *-------------------------------------------------------------------------
+  */
+ #include "postgres.h"
+ 
+ #include "access/amvalidate.h"
+ #include "access/htup_details.h"
+ #include "catalog/pg_amop.h"
+ #include "catalog/pg_amproc.h"
+ #include "catalog/pg_opclass.h"
+ #include "catalog/pg_opfamily.h"
+ #include "catalog/pg_type.h"
+ #include "utils/builtins.h"
+ #include "utils/lsyscache.h"
+ #include "utils/syscache.h"
+ 
+ #include "bloom.h"
+ 
+ /*
+  * Validator for a bloom opclass.
+  */
+ bool
+ blvalidate(Oid opclassoid)
+ {
+ 	bool		result = true;
+ 	HeapTuple	classtup;
+ 	Form_pg_opclass classform;
+ 	Oid			opfamilyoid;
+ 	Oid			opcintype;
+ 	Oid			opckeytype;
+ 	char	   *opclassname;
+ 	HeapTuple	familytup;
+ 	Form_pg_opfamily familyform;
+ 	char	   *opfamilyname;
+ 	CatCList   *proclist,
+ 			   *oprlist;
+ 	List	   *grouplist;
+ 	OpFamilyOpFuncGroup *opclassgroup;
+ 	int			i;
+ 	ListCell   *lc;
+ 
+ 	/* Fetch opclass information */
+ 	classtup = SearchSysCache1(CLAOID, ObjectIdGetDatum(opclassoid));
+ 	if (!HeapTupleIsValid(classtup))
+ 		elog(ERROR, "cache lookup failed for operator class %u", opclassoid);
+ 	classform = (Form_pg_opclass) GETSTRUCT(classtup);
+ 
+ 	opfamilyoid = classform->opcfamily;
+ 	opcintype = classform->opcintype;
+ 	opckeytype = classform->opckeytype;
+ 	if (!OidIsValid(opckeytype))
+ 		opckeytype = opcintype;
+ 	opclassname = NameStr(classform->opcname);
+ 
+ 	/* Fetch opfamily information */
+ 	familytup = SearchSysCache1(OPFAMILYOID, ObjectIdGetDatum(opfamilyoid));
+ 	if (!HeapTupleIsValid(familytup))
+ 		elog(ERROR, "cache lookup failed for operator family %u", opfamilyoid);
+ 	familyform = (Form_pg_opfamily) GETSTRUCT(familytup);
+ 
+ 	opfamilyname = NameStr(familyform->opfname);
+ 
+ 	/* Fetch all operators and support functions of the opfamily */
+ 	oprlist = SearchSysCacheList1(AMOPSTRATEGY, ObjectIdGetDatum(opfamilyoid));
+ 	proclist = SearchSysCacheList1(AMPROCNUM, ObjectIdGetDatum(opfamilyoid));
+ 
+ 	/* Check individual support functions */
+ 	for (i = 0; i < proclist->n_members; i++)
+ 	{
+ 		HeapTuple	proctup = &proclist->members[i]->tuple;
+ 		Form_pg_amproc procform = (Form_pg_amproc) GETSTRUCT(proctup);
+ 		bool		ok;
+ 
+ 		/*
+ 		 * All bloom support functions should be registered with matching
+ 		 * left/right types
+ 		 */
+ 		if (procform->amproclefttype != procform->amprocrighttype)
+ 		{
+ 			ereport(INFO,
+ 					(errcode(ERRCODE_INVALID_OBJECT_DEFINITION),
+ 					 errmsg("bloom opfamily %s contains support procedure %s with cross-type registration",
+ 							opfamilyname,
+ 							format_procedure(procform->amproc))));
+ 			result = false;
+ 		}
+ 
+ 		/*
+ 		 * We can't check signatures except within the specific opclass, since
+ 		 * we need to know the associated opckeytype in many cases.
+ 		 */
+ 		if (procform->amproclefttype != opcintype)
+ 			continue;
+ 
+ 		/* Check procedure numbers and function signatures */
+ 		switch (procform->amprocnum)
+ 		{
+ 			case BLOOM_HASH_PROC:
+ 				ok = check_amproc_signature(procform->amproc, INT4OID, false,
+ 											1, 1, opckeytype);
+ 				break;
+ 			default:
+ 				ereport(INFO,
+ 						(errcode(ERRCODE_INVALID_OBJECT_DEFINITION),
+ 						 errmsg("bloom opfamily %s contains function %s with invalid support number %d",
+ 								opfamilyname,
+ 								format_procedure(procform->amproc),
+ 								procform->amprocnum)));
+ 				result = false;
+ 				continue;		/* don't want additional message */
+ 		}
+ 
+ 		if (!ok)
+ 		{
+ 			ereport(INFO,
+ 					(errcode(ERRCODE_INVALID_OBJECT_DEFINITION),
+ 					 errmsg("gist opfamily %s contains function %s with wrong signature for support number %d",
+ 							opfamilyname,
+ 							format_procedure(procform->amproc),
+ 							procform->amprocnum)));
+ 			result = false;
+ 		}
+ 	}
+ 
+ 	/* Check individual operators */
+ 	for (i = 0; i < oprlist->n_members; i++)
+ 	{
+ 		HeapTuple	oprtup = &oprlist->members[i]->tuple;
+ 		Form_pg_amop oprform = (Form_pg_amop) GETSTRUCT(oprtup);
+ 
+ 		/* Check it's allowed strategy for bloom */
+ 		if (oprform->amopstrategy < 1 || 
+ 			oprform->amopstrategy > BLOOM_NSTRATEGIES)
+ 		{
+ 			ereport(INFO,
+ 					(errcode(ERRCODE_INVALID_OBJECT_DEFINITION),
+ 					 errmsg("bloom opfamily %s contains operator %s with invalid strategy number %d",
+ 							opfamilyname,
+ 							format_operator(oprform->amopopr),
+ 							oprform->amopstrategy)));
+ 			result = false;
+ 		}
+ 
+ 		/* bloom doesn't support ORDER BY operators */
+ 		if (oprform->amoppurpose != AMOP_SEARCH ||
+ 			OidIsValid(oprform->amopsortfamily))
+ 		{
+ 			ereport(INFO,
+ 					(errcode(ERRCODE_INVALID_OBJECT_DEFINITION),
+ 					 errmsg("bloom opfamily %s contains invalid ORDER BY specification for operator %s",
+ 							opfamilyname,
+ 							format_operator(oprform->amopopr))));
+ 			result = false;
+ 		}
+ 
+ 		/* Check operator signature --- same for all bloom strategies */
+ 		if (!check_amop_signature(oprform->amopopr, BOOLOID,
+ 								  oprform->amoplefttype,
+ 								  oprform->amoprighttype))
+ 		{
+ 			ereport(INFO,
+ 					(errcode(ERRCODE_INVALID_OBJECT_DEFINITION),
+ 					 errmsg("bloom opfamily %s contains operator %s with wrong signature",
+ 							opfamilyname,
+ 							format_operator(oprform->amopopr))));
+ 			result = false;
+ 		}
+ 	}
+ 
+ 	/* Now check for inconsistent groups of operators/functions */
+ 	grouplist = identify_opfamily_groups(oprlist, proclist);
+ 	opclassgroup = NULL;
+ 	foreach(lc, grouplist)
+ 	{
+ 		OpFamilyOpFuncGroup *thisgroup = (OpFamilyOpFuncGroup *) lfirst(lc);
+ 
+ 		/* Remember the group exactly matching the test opclass */
+ 		if (thisgroup->lefttype == opcintype &&
+ 			thisgroup->righttype == opcintype)
+ 			opclassgroup = thisgroup;
+ 
+ 		/*
+ 		 * There is not a lot we can do to check the operator sets, since each
+ 		 * bloom opclass is more or less a law unto itself, and some contain
+ 		 * only operators that are binary-compatible with the opclass datatype
+ 		 * (meaning that empty operator sets can be OK).  That case also means
+ 		 * that we shouldn't insist on nonempty function sets except for the
+ 		 * opclass's own group.
+ 		 */
+ 	}
+ 
+ 	/* Check that the originally-named opclass is complete */
+ 	for (i = 1; i <= BLOOM_NPROC; i++)
+ 	{
+ 		if (opclassgroup &&
+ 			(opclassgroup->functionset & (((uint64) 1) << i)) != 0)
+ 			continue;			/* got it */
+ 		ereport(INFO,
+ 				(errcode(ERRCODE_INVALID_OBJECT_DEFINITION),
+ 				 errmsg("bloom opclass %s is missing support function %d",
+ 						opclassname, i)));
+ 		result = false;
+ 	}
+ 
+ 	ReleaseCatCacheList(proclist);
+ 	ReleaseCatCacheList(oprlist);
+ 	ReleaseSysCache(familytup);
+ 	ReleaseSysCache(classtup);
+ 
+ 	return result;
+ }
diff --git a/contrib/bloom/data/data b/contrib/bloom/data/data
new file mode 100644
index ...eacf3e7
*** a/contrib/bloom/data/data
--- b/contrib/bloom/data/data
***************
*** 0 ****
--- 1,10000 ----
+ 739	3
+ 475	9
+ 45	6
+ 433	1
+ 948	8
+ 926	8
+ 397	7
+ 980	4
+ 212	5
+ 522	9
+ 74	8
+ 77	4
+ 378	9
+ 575	3
+ 625	2
+ 407	4
+ 509	9
+ 252	6
+ 487	7
+ 656	4
+ 485	6
+ 275	9
+ 285	3
+ 277	5
+ 804	8
+ 424	9
+ 553	5
+ 245	9
+ 384	8
+ 202	0
+ 43	6
+ 374	6
+ 490	6
+ 105	10
+ 311	8
+ 411	8
+ 343	7
+ 678	6
+ 942	10
+ 126	7
+ 755	6
+ 625	3
+ 52	9
+ 239	4
+ 690	4
+ 445	7
+ 49	8
+ 285	5
+ 445	4
+ 516	8
+ 151	9
+ 553	5
+ 613	2
+ 123	6
+ 187	2
+ 301	9
+ 800	9
+ 250	9
+ 796	5
+ 288	5
+ 930	7
+ 219	10
+ 553	5
+ 518	10
+ 893	0
+ 754	0
+ 960	3
+ 538	6
+ 537	7
+ 127	7
+ 910	4
+ 666	7
+ 354	9
+ 562	1
+ 405	8
+ 635	3
+ 583	9
+ 313	1
+ 358	8
+ 133	3
+ 864	9
+ 296	8
+ 193	8
+ 396	7
+ 495	5
+ 454	4
+ 952	1
+ 115	3
+ 36	7
+ 455	4
+ 527	1
+ 775	1
+ 945	1
+ 246	3
+ 920	4
+ 554	8
+ 267	8
+ 608	5
+ 684	0
+ 190	2
+ 527	6
+ 584	5
+ 764	7
+ 785	8
+ 376	2
+ 240	9
+ 330	0
+ 13	3
+ 103	3
+ 578	0
+ 639	1
+ 807	9
+ 982	4
+ 365	7
+ 418	6
+ 844	9
+ 199	4
+ 425	10
+ 127	2
+ 762	5
+ 450	0
+ 406	8
+ 17	4
+ 55	1
+ 678	6
+ 143	3
+ 764	9
+ 222	7
+ 364	6
+ 411	8
+ 142	3
+ 728	3
+ 684	2
+ 303	8
+ 363	1
+ 314	8
+ 67	7
+ 592	1
+ 139	6
+ 204	8
+ 279	3
+ 133	0
+ 296	4
+ 788	7
+ 942	2
+ 441	1
+ 454	2
+ 424	1
+ 322	7
+ 949	7
+ 793	3
+ 497	9
+ 984	1
+ 944	1
+ 736	1
+ 940	0
+ 494	1
+ 57	8
+ 429	8
+ 449	4
+ 44	9
+ 454	5
+ 60	9
+ 636	4
+ 606	6
+ 67	4
+ 848	6
+ 259	8
+ 654	2
+ 955	4
+ 351	9
+ 405	8
+ 968	5
+ 634	4
+ 308	1
+ 767	4
+ 974	2
+ 850	0
+ 99	5
+ 416	7
+ 71	5
+ 103	9
+ 48	4
+ 750	7
+ 565	7
+ 92	9
+ 599	5
+ 760	6
+ 960	4
+ 964	3
+ 478	7
+ 620	5
+ 953	5
+ 485	1
+ 957	9
+ 756	0
+ 383	9
+ 946	4
+ 222	7
+ 133	8
+ 401	2
+ 702	0
+ 723	5
+ 568	7
+ 857	5
+ 951	3
+ 264	6
+ 786	2
+ 42	3
+ 268	10
+ 172	0
+ 26	6
+ 884	10
+ 986	1
+ 667	1
+ 893	1
+ 344	6
+ 68	1
+ 58	6
+ 750	9
+ 168	7
+ 249	4
+ 273	0
+ 649	3
+ 306	9
+ 314	5
+ 942	3
+ 33	8
+ 311	0
+ 932	10
+ 138	8
+ 47	5
+ 420	1
+ 550	5
+ 751	3
+ 392	9
+ 1	6
+ 351	3
+ 677	10
+ 588	10
+ 917	9
+ 461	9
+ 242	5
+ 685	6
+ 514	6
+ 531	7
+ 442	6
+ 135	9
+ 693	7
+ 341	4
+ 984	7
+ 362	10
+ 375	7
+ 259	1
+ 713	8
+ 35	6
+ 750	5
+ 489	10
+ 991	2
+ 544	5
+ 791	1
+ 156	2
+ 653	3
+ 96	3
+ 976	4
+ 789	10
+ 170	2
+ 946	5
+ 865	2
+ 597	6
+ 53	6
+ 209	8
+ 128	7
+ 794	1
+ 871	3
+ 623	7
+ 413	8
+ 895	1
+ 70	10
+ 411	0
+ 428	2
+ 6	6
+ 352	10
+ 143	2
+ 156	7
+ 795	2
+ 372	0
+ 11	5
+ 701	8
+ 619	6
+ 142	2
+ 233	6
+ 20	1
+ 621	1
+ 118	0
+ 136	5
+ 232	1
+ 145	6
+ 93	3
+ 800	2
+ 28	6
+ 457	4
+ 598	5
+ 900	3
+ 273	5
+ 870	4
+ 760	1
+ 970	8
+ 231	6
+ 871	3
+ 622	0
+ 895	9
+ 148	0
+ 439	2
+ 328	2
+ 489	4
+ 834	9
+ 756	4
+ 415	7
+ 730	7
+ 175	6
+ 102	9
+ 703	1
+ 715	9
+ 662	6
+ 283	3
+ 592	2
+ 139	7
+ 218	6
+ 981	5
+ 816	5
+ 902	7
+ 417	7
+ 82	8
+ 314	8
+ 519	5
+ 413	6
+ 424	1
+ 693	1
+ 50	4
+ 725	3
+ 639	3
+ 511	8
+ 58	7
+ 356	0
+ 275	2
+ 510	2
+ 822	9
+ 835	9
+ 759	1
+ 717	3
+ 639	1
+ 899	1
+ 246	6
+ 202	3
+ 946	9
+ 629	6
+ 245	1
+ 363	3
+ 870	7
+ 342	1
+ 891	9
+ 322	7
+ 778	2
+ 617	5
+ 307	3
+ 814	9
+ 463	7
+ 8	7
+ 304	2
+ 5	2
+ 138	6
+ 835	4
+ 774	2
+ 685	6
+ 916	0
+ 789	8
+ 878	1
+ 519	7
+ 269	1
+ 193	6
+ 470	0
+ 522	9
+ 720	5
+ 643	0
+ 741	6
+ 275	9
+ 282	1
+ 261	1
+ 306	9
+ 701	2
+ 973	5
+ 28	9
+ 602	5
+ 507	9
+ 683	7
+ 448	2
+ 708	10
+ 88	4
+ 501	7
+ 453	2
+ 379	7
+ 120	7
+ 836	4
+ 717	1
+ 327	4
+ 365	3
+ 908	4
+ 151	5
+ 940	7
+ 381	6
+ 359	8
+ 777	1
+ 799	9
+ 495	3
+ 595	9
+ 542	10
+ 675	7
+ 634	5
+ 44	4
+ 654	4
+ 769	0
+ 671	7
+ 411	8
+ 187	4
+ 481	6
+ 974	8
+ 398	8
+ 907	2
+ 615	4
+ 497	2
+ 349	0
+ 183	0
+ 701	8
+ 535	7
+ 169	2
+ 116	9
+ 208	8
+ 615	6
+ 610	8
+ 970	1
+ 371	9
+ 931	8
+ 695	8
+ 966	3
+ 239	5
+ 520	6
+ 502	7
+ 612	2
+ 520	1
+ 948	7
+ 337	1
+ 627	5
+ 852	2
+ 165	5
+ 45	1
+ 554	4
+ 79	5
+ 185	8
+ 323	2
+ 84	6
+ 613	6
+ 151	1
+ 306	8
+ 318	8
+ 911	3
+ 516	2
+ 331	1
+ 793	2
+ 385	10
+ 646	4
+ 92	2
+ 846	2
+ 686	0
+ 945	0
+ 181	0
+ 572	8
+ 633	7
+ 909	9
+ 486	2
+ 766	4
+ 493	3
+ 645	8
+ 424	4
+ 8	8
+ 395	7
+ 240	5
+ 855	1
+ 659	5
+ 117	6
+ 551	3
+ 634	1
+ 93	3
+ 846	0
+ 206	3
+ 228	10
+ 730	7
+ 253	4
+ 546	7
+ 813	6
+ 487	2
+ 209	7
+ 696	1
+ 814	4
+ 605	9
+ 959	2
+ 230	6
+ 278	3
+ 860	1
+ 324	1
+ 457	6
+ 37	2
+ 273	3
+ 561	8
+ 968	4
+ 373	5
+ 582	6
+ 183	3
+ 646	10
+ 633	3
+ 928	6
+ 407	2
+ 185	7
+ 480	0
+ 810	8
+ 111	3
+ 355	1
+ 453	6
+ 439	0
+ 447	4
+ 388	8
+ 862	10
+ 402	0
+ 247	0
+ 42	9
+ 299	10
+ 472	7
+ 127	7
+ 392	6
+ 702	2
+ 410	8
+ 468	8
+ 960	9
+ 394	4
+ 935	8
+ 806	3
+ 661	7
+ 292	1
+ 714	5
+ 111	8
+ 419	4
+ 725	9
+ 117	9
+ 548	5
+ 460	2
+ 711	9
+ 62	2
+ 636	0
+ 99	0
+ 421	0
+ 870	2
+ 357	5
+ 896	6
+ 594	6
+ 189	7
+ 365	6
+ 116	1
+ 499	2
+ 943	0
+ 742	4
+ 297	5
+ 273	4
+ 631	9
+ 382	7
+ 938	8
+ 765	8
+ 30	1
+ 338	9
+ 771	9
+ 535	10
+ 637	9
+ 568	8
+ 990	1
+ 986	9
+ 114	7
+ 335	4
+ 181	6
+ 770	8
+ 517	2
+ 543	5
+ 954	3
+ 262	10
+ 430	6
+ 910	2
+ 531	4
+ 160	2
+ 345	7
+ 921	3
+ 795	9
+ 267	9
+ 635	6
+ 319	8
+ 211	1
+ 628	7
+ 240	2
+ 182	2
+ 479	4
+ 179	9
+ 43	1
+ 110	6
+ 535	3
+ 743	9
+ 999	7
+ 214	8
+ 571	5
+ 702	2
+ 85	0
+ 22	3
+ 111	6
+ 23	4
+ 821	2
+ 546	3
+ 648	7
+ 210	7
+ 814	3
+ 267	3
+ 590	0
+ 228	6
+ 674	4
+ 382	2
+ 924	1
+ 450	0
+ 106	5
+ 304	2
+ 121	3
+ 568	9
+ 532	1
+ 243	2
+ 839	5
+ 872	7
+ 772	1
+ 2	4
+ 148	2
+ 950	8
+ 673	3
+ 66	6
+ 416	5
+ 606	5
+ 987	9
+ 739	1
+ 237	3
+ 51	8
+ 422	3
+ 949	3
+ 746	8
+ 914	5
+ 959	9
+ 880	1
+ 146	8
+ 929	8
+ 163	10
+ 416	6
+ 511	0
+ 102	5
+ 932	8
+ 606	2
+ 149	7
+ 939	6
+ 951	9
+ 831	7
+ 710	7
+ 215	7
+ 662	1
+ 777	8
+ 926	7
+ 627	1
+ 701	0
+ 668	2
+ 66	8
+ 709	10
+ 611	3
+ 168	8
+ 973	1
+ 330	9
+ 996	2
+ 620	7
+ 907	8
+ 375	6
+ 931	2
+ 377	9
+ 857	0
+ 945	6
+ 49	6
+ 769	1
+ 384	5
+ 113	10
+ 794	3
+ 756	8
+ 389	1
+ 690	4
+ 248	3
+ 90	2
+ 146	5
+ 724	1
+ 616	1
+ 933	5
+ 106	9
+ 31	2
+ 492	8
+ 270	9
+ 279	4
+ 872	1
+ 664	6
+ 840	1
+ 713	5
+ 438	10
+ 841	5
+ 116	10
+ 994	8
+ 63	6
+ 942	10
+ 83	0
+ 874	1
+ 203	4
+ 914	5
+ 242	2
+ 856	1
+ 265	5
+ 742	1
+ 573	5
+ 635	0
+ 416	5
+ 540	5
+ 462	5
+ 373	5
+ 143	3
+ 520	2
+ 363	4
+ 340	6
+ 760	3
+ 40	0
+ 446	9
+ 117	7
+ 416	9
+ 816	10
+ 313	5
+ 0	7
+ 927	5
+ 261	4
+ 74	6
+ 914	2
+ 949	4
+ 443	3
+ 829	8
+ 879	6
+ 37	9
+ 591	5
+ 814	7
+ 195	2
+ 566	0
+ 218	9
+ 462	2
+ 608	4
+ 759	9
+ 778	8
+ 504	7
+ 49	5
+ 127	5
+ 765	10
+ 276	6
+ 544	3
+ 562	1
+ 797	4
+ 843	10
+ 605	4
+ 2	8
+ 288	5
+ 42	9
+ 853	8
+ 765	6
+ 633	3
+ 324	7
+ 722	5
+ 175	5
+ 406	5
+ 130	9
+ 765	7
+ 85	6
+ 68	9
+ 553	7
+ 337	6
+ 497	6
+ 19	5
+ 520	9
+ 340	3
+ 504	10
+ 554	8
+ 656	3
+ 279	8
+ 763	7
+ 283	9
+ 634	0
+ 585	7
+ 609	7
+ 647	2
+ 326	10
+ 717	8
+ 608	7
+ 362	1
+ 608	7
+ 413	1
+ 676	10
+ 940	3
+ 244	2
+ 163	0
+ 903	4
+ 899	5
+ 494	5
+ 256	1
+ 136	9
+ 264	5
+ 886	10
+ 285	5
+ 717	6
+ 621	3
+ 349	0
+ 436	0
+ 2	4
+ 356	2
+ 595	5
+ 251	5
+ 965	2
+ 34	5
+ 633	3
+ 562	8
+ 192	8
+ 231	1
+ 807	5
+ 571	5
+ 163	2
+ 848	5
+ 226	3
+ 536	2
+ 661	9
+ 473	3
+ 412	7
+ 753	4
+ 874	8
+ 837	5
+ 77	4
+ 277	3
+ 225	5
+ 347	0
+ 24	9
+ 555	2
+ 109	4
+ 699	3
+ 688	2
+ 563	3
+ 128	0
+ 604	5
+ 759	4
+ 919	6
+ 143	8
+ 141	2
+ 154	4
+ 488	4
+ 926	8
+ 410	10
+ 752	10
+ 137	9
+ 369	8
+ 197	1
+ 72	8
+ 405	2
+ 795	0
+ 741	6
+ 365	7
+ 187	5
+ 415	3
+ 728	6
+ 745	2
+ 948	7
+ 51	4
+ 621	8
+ 324	8
+ 665	7
+ 595	9
+ 750	7
+ 622	2
+ 867	4
+ 164	6
+ 971	5
+ 267	2
+ 38	7
+ 485	8
+ 251	2
+ 982	2
+ 902	0
+ 556	5
+ 836	9
+ 282	5
+ 573	9
+ 364	3
+ 543	10
+ 477	4
+ 403	6
+ 18	4
+ 171	3
+ 531	2
+ 966	0
+ 974	2
+ 247	10
+ 415	1
+ 988	10
+ 672	8
+ 851	10
+ 325	4
+ 830	7
+ 746	4
+ 675	2
+ 784	1
+ 865	8
+ 450	0
+ 86	10
+ 244	1
+ 998	2
+ 269	2
+ 173	7
+ 394	2
+ 655	1
+ 986	5
+ 20	3
+ 930	8
+ 0	7
+ 224	7
+ 900	0
+ 752	8
+ 809	2
+ 800	9
+ 184	0
+ 947	2
+ 261	2
+ 427	4
+ 899	8
+ 596	6
+ 887	6
+ 60	9
+ 894	10
+ 757	9
+ 667	10
+ 569	6
+ 987	3
+ 331	8
+ 524	1
+ 691	7
+ 174	6
+ 891	4
+ 854	3
+ 870	8
+ 139	5
+ 307	0
+ 48	4
+ 933	9
+ 358	7
+ 836	0
+ 670	4
+ 591	7
+ 726	9
+ 454	3
+ 53	1
+ 959	2
+ 783	8
+ 663	6
+ 168	5
+ 389	3
+ 999	7
+ 334	0
+ 64	3
+ 989	4
+ 957	8
+ 447	6
+ 231	0
+ 285	10
+ 960	7
+ 208	0
+ 883	2
+ 240	7
+ 16	9
+ 302	2
+ 435	7
+ 490	4
+ 388	8
+ 481	5
+ 91	5
+ 874	0
+ 296	3
+ 675	5
+ 359	10
+ 484	3
+ 698	7
+ 332	6
+ 858	6
+ 247	9
+ 475	5
+ 57	9
+ 241	5
+ 344	6
+ 371	8
+ 81	5
+ 296	10
+ 509	6
+ 277	2
+ 120	6
+ 143	6
+ 955	8
+ 296	3
+ 421	2
+ 860	7
+ 28	3
+ 217	1
+ 244	5
+ 632	6
+ 87	0
+ 414	2
+ 465	7
+ 123	10
+ 303	4
+ 158	4
+ 36	3
+ 27	10
+ 142	3
+ 278	6
+ 476	1
+ 231	5
+ 472	4
+ 588	7
+ 907	2
+ 305	10
+ 223	7
+ 161	7
+ 428	3
+ 662	7
+ 684	8
+ 154	7
+ 121	2
+ 711	3
+ 503	10
+ 826	10
+ 127	1
+ 483	6
+ 506	1
+ 316	4
+ 292	6
+ 407	5
+ 339	6
+ 203	8
+ 853	9
+ 499	5
+ 684	7
+ 257	8
+ 833	10
+ 68	3
+ 958	9
+ 316	1
+ 950	8
+ 685	5
+ 870	0
+ 869	2
+ 622	3
+ 676	10
+ 844	9
+ 729	7
+ 743	2
+ 234	4
+ 881	5
+ 233	7
+ 460	3
+ 51	4
+ 193	4
+ 503	1
+ 165	2
+ 600	0
+ 189	5
+ 197	8
+ 745	9
+ 773	6
+ 752	5
+ 285	5
+ 730	5
+ 923	6
+ 10	2
+ 324	5
+ 455	4
+ 888	6
+ 741	4
+ 792	9
+ 579	4
+ 942	8
+ 862	1
+ 580	6
+ 12	4
+ 196	8
+ 854	5
+ 259	6
+ 1	2
+ 195	0
+ 336	5
+ 481	8
+ 894	4
+ 440	6
+ 760	2
+ 542	3
+ 625	5
+ 107	5
+ 622	7
+ 94	6
+ 40	3
+ 397	9
+ 771	7
+ 479	8
+ 837	7
+ 783	2
+ 192	3
+ 964	1
+ 633	4
+ 721	4
+ 637	3
+ 732	3
+ 746	8
+ 749	4
+ 527	8
+ 2	6
+ 133	4
+ 462	9
+ 54	9
+ 677	9
+ 613	5
+ 64	8
+ 725	0
+ 891	4
+ 433	6
+ 751	1
+ 876	5
+ 332	6
+ 324	1
+ 990	9
+ 925	10
+ 418	1
+ 390	9
+ 962	4
+ 820	6
+ 335	4
+ 99	4
+ 239	8
+ 427	1
+ 182	9
+ 743	9
+ 930	6
+ 418	3
+ 241	7
+ 344	2
+ 593	3
+ 223	0
+ 326	6
+ 891	3
+ 58	7
+ 928	4
+ 145	0
+ 792	4
+ 851	2
+ 514	0
+ 80	3
+ 967	0
+ 875	4
+ 272	1
+ 126	6
+ 347	7
+ 884	6
+ 730	2
+ 184	6
+ 498	2
+ 333	4
+ 635	5
+ 453	4
+ 861	3
+ 647	4
+ 338	7
+ 632	3
+ 736	5
+ 689	0
+ 624	8
+ 623	10
+ 534	5
+ 541	3
+ 717	7
+ 885	2
+ 967	2
+ 641	6
+ 696	1
+ 29	6
+ 399	7
+ 933	7
+ 403	6
+ 41	1
+ 73	7
+ 147	7
+ 546	8
+ 668	1
+ 278	2
+ 344	10
+ 934	2
+ 209	9
+ 447	8
+ 503	1
+ 944	5
+ 700	3
+ 208	6
+ 79	6
+ 198	1
+ 750	3
+ 851	9
+ 967	4
+ 668	6
+ 477	9
+ 843	8
+ 940	8
+ 51	1
+ 678	5
+ 999	2
+ 641	9
+ 713	3
+ 285	9
+ 974	4
+ 532	2
+ 485	3
+ 442	3
+ 179	4
+ 733	8
+ 44	2
+ 792	9
+ 32	7
+ 664	1
+ 880	3
+ 581	9
+ 523	2
+ 822	2
+ 563	1
+ 157	5
+ 471	7
+ 709	10
+ 971	2
+ 292	2
+ 561	0
+ 997	6
+ 236	8
+ 491	3
+ 521	2
+ 351	4
+ 498	9
+ 281	0
+ 153	1
+ 258	7
+ 209	4
+ 253	7
+ 105	10
+ 636	1
+ 113	9
+ 227	7
+ 954	2
+ 278	2
+ 14	8
+ 459	5
+ 926	8
+ 937	4
+ 742	2
+ 446	9
+ 320	7
+ 611	5
+ 120	9
+ 210	2
+ 827	8
+ 301	9
+ 775	5
+ 614	7
+ 753	9
+ 918	8
+ 663	4
+ 302	6
+ 187	2
+ 13	9
+ 457	5
+ 824	8
+ 163	4
+ 307	3
+ 300	5
+ 508	1
+ 363	8
+ 67	1
+ 338	7
+ 866	1
+ 573	8
+ 858	2
+ 161	2
+ 824	3
+ 399	8
+ 277	9
+ 295	1
+ 633	5
+ 536	9
+ 742	8
+ 456	3
+ 963	8
+ 61	0
+ 956	4
+ 710	8
+ 490	3
+ 606	3
+ 519	8
+ 508	3
+ 116	9
+ 179	4
+ 762	5
+ 494	4
+ 934	0
+ 335	7
+ 867	8
+ 926	8
+ 610	10
+ 859	6
+ 386	6
+ 389	9
+ 852	10
+ 224	4
+ 763	7
+ 713	9
+ 638	9
+ 272	4
+ 367	8
+ 796	3
+ 796	1
+ 977	7
+ 921	9
+ 493	5
+ 890	4
+ 98	3
+ 921	5
+ 152	8
+ 482	4
+ 143	2
+ 108	9
+ 124	7
+ 750	4
+ 147	1
+ 162	9
+ 418	10
+ 73	4
+ 622	10
+ 298	1
+ 526	2
+ 466	6
+ 464	4
+ 111	6
+ 159	6
+ 992	3
+ 837	1
+ 159	10
+ 847	9
+ 357	10
+ 26	5
+ 937	4
+ 478	0
+ 839	1
+ 5	1
+ 214	5
+ 325	7
+ 156	8
+ 66	3
+ 405	2
+ 859	4
+ 527	7
+ 498	7
+ 658	3
+ 595	0
+ 339	6
+ 535	3
+ 65	0
+ 286	9
+ 112	3
+ 41	3
+ 823	4
+ 6	10
+ 154	1
+ 245	6
+ 295	1
+ 957	8
+ 800	5
+ 508	5
+ 801	1
+ 473	1
+ 723	0
+ 415	8
+ 21	7
+ 691	1
+ 993	7
+ 460	8
+ 97	5
+ 795	3
+ 536	0
+ 811	8
+ 144	8
+ 654	9
+ 224	2
+ 403	0
+ 263	9
+ 165	10
+ 884	6
+ 774	9
+ 282	5
+ 39	3
+ 197	5
+ 91	3
+ 964	9
+ 546	5
+ 926	4
+ 332	1
+ 127	10
+ 15	4
+ 146	4
+ 376	4
+ 293	5
+ 396	2
+ 120	2
+ 83	4
+ 636	1
+ 677	8
+ 620	8
+ 128	6
+ 655	7
+ 84	6
+ 32	4
+ 651	2
+ 400	7
+ 510	5
+ 83	9
+ 957	4
+ 426	4
+ 554	5
+ 523	6
+ 949	2
+ 758	6
+ 992	4
+ 395	1
+ 962	0
+ 794	0
+ 630	8
+ 461	3
+ 984	9
+ 947	5
+ 408	0
+ 380	4
+ 407	8
+ 717	10
+ 352	2
+ 598	3
+ 399	4
+ 927	4
+ 734	3
+ 510	7
+ 371	3
+ 742	0
+ 129	2
+ 283	1
+ 63	2
+ 608	5
+ 261	10
+ 835	7
+ 793	6
+ 628	1
+ 793	2
+ 446	2
+ 582	4
+ 583	3
+ 695	1
+ 13	1
+ 397	8
+ 68	5
+ 957	4
+ 641	0
+ 582	2
+ 491	8
+ 235	3
+ 510	0
+ 879	1
+ 173	7
+ 365	6
+ 863	9
+ 992	4
+ 264	7
+ 540	3
+ 754	9
+ 32	8
+ 464	10
+ 174	1
+ 9	8
+ 353	5
+ 598	6
+ 827	1
+ 616	7
+ 247	8
+ 377	6
+ 407	2
+ 558	4
+ 686	8
+ 86	2
+ 99	8
+ 163	1
+ 662	6
+ 120	8
+ 731	1
+ 591	1
+ 630	2
+ 671	5
+ 298	3
+ 162	5
+ 75	5
+ 155	5
+ 779	7
+ 880	5
+ 535	10
+ 691	6
+ 806	9
+ 764	5
+ 480	9
+ 303	2
+ 13	9
+ 294	6
+ 84	10
+ 100	4
+ 252	3
+ 926	3
+ 801	1
+ 808	6
+ 794	7
+ 45	3
+ 655	7
+ 963	5
+ 589	7
+ 929	1
+ 611	2
+ 279	6
+ 127	6
+ 267	2
+ 538	4
+ 592	8
+ 629	5
+ 117	4
+ 599	9
+ 10	4
+ 614	1
+ 722	3
+ 790	7
+ 730	4
+ 413	7
+ 447	0
+ 891	7
+ 648	0
+ 299	9
+ 228	8
+ 282	8
+ 627	9
+ 338	7
+ 340	9
+ 669	3
+ 330	3
+ 404	1
+ 552	2
+ 738	3
+ 574	2
+ 941	0
+ 174	8
+ 747	8
+ 849	0
+ 738	1
+ 884	0
+ 897	5
+ 931	2
+ 256	3
+ 173	9
+ 621	5
+ 209	0
+ 556	8
+ 220	3
+ 43	8
+ 444	10
+ 815	6
+ 816	6
+ 441	7
+ 609	2
+ 742	5
+ 199	6
+ 4	1
+ 875	3
+ 400	0
+ 185	0
+ 551	4
+ 46	1
+ 155	3
+ 400	2
+ 60	8
+ 183	9
+ 463	10
+ 436	9
+ 665	0
+ 82	4
+ 538	3
+ 47	5
+ 410	9
+ 802	8
+ 970	10
+ 832	5
+ 381	9
+ 627	5
+ 145	0
+ 734	2
+ 872	9
+ 79	3
+ 916	5
+ 238	6
+ 560	3
+ 988	1
+ 602	0
+ 639	0
+ 956	4
+ 823	9
+ 429	7
+ 446	8
+ 533	1
+ 346	7
+ 101	1
+ 883	10
+ 997	10
+ 307	9
+ 477	5
+ 495	0
+ 865	5
+ 135	5
+ 517	8
+ 479	5
+ 215	3
+ 399	6
+ 957	8
+ 454	5
+ 919	8
+ 168	0
+ 880	1
+ 992	9
+ 13	3
+ 791	5
+ 844	3
+ 527	7
+ 768	7
+ 176	3
+ 435	7
+ 759	7
+ 957	2
+ 295	9
+ 4	7
+ 403	9
+ 548	6
+ 943	4
+ 622	9
+ 305	6
+ 235	1
+ 124	1
+ 381	7
+ 789	1
+ 312	10
+ 434	7
+ 619	2
+ 398	6
+ 351	7
+ 489	4
+ 442	9
+ 279	10
+ 463	2
+ 418	1
+ 158	7
+ 720	4
+ 819	8
+ 473	2
+ 496	3
+ 349	8
+ 226	8
+ 556	8
+ 976	10
+ 421	3
+ 648	9
+ 683	1
+ 803	10
+ 80	3
+ 184	5
+ 352	3
+ 221	1
+ 736	0
+ 917	2
+ 240	4
+ 470	6
+ 221	7
+ 372	8
+ 542	3
+ 731	10
+ 676	4
+ 874	4
+ 469	7
+ 321	5
+ 943	5
+ 46	3
+ 848	3
+ 367	6
+ 307	3
+ 793	5
+ 697	3
+ 135	9
+ 959	5
+ 695	5
+ 855	4
+ 464	5
+ 806	3
+ 890	3
+ 14	2
+ 822	10
+ 715	9
+ 253	6
+ 135	6
+ 147	4
+ 904	9
+ 988	6
+ 203	1
+ 519	2
+ 630	2
+ 663	5
+ 640	1
+ 16	4
+ 465	9
+ 720	5
+ 115	5
+ 437	8
+ 410	7
+ 393	5
+ 309	5
+ 987	2
+ 479	10
+ 814	7
+ 97	3
+ 844	7
+ 547	5
+ 212	2
+ 634	2
+ 634	1
+ 133	4
+ 579	2
+ 896	0
+ 79	3
+ 706	5
+ 852	0
+ 12	8
+ 228	5
+ 813	0
+ 173	9
+ 376	0
+ 637	9
+ 524	8
+ 111	2
+ 76	7
+ 258	2
+ 98	8
+ 457	10
+ 853	5
+ 301	6
+ 8	2
+ 574	0
+ 991	8
+ 511	8
+ 845	7
+ 713	2
+ 702	4
+ 144	2
+ 199	3
+ 385	3
+ 999	6
+ 483	1
+ 481	9
+ 91	3
+ 475	4
+ 893	5
+ 544	5
+ 503	5
+ 270	0
+ 338	1
+ 698	1
+ 336	4
+ 402	5
+ 626	6
+ 735	0
+ 875	7
+ 655	4
+ 830	1
+ 298	9
+ 469	8
+ 313	4
+ 256	9
+ 830	8
+ 392	1
+ 773	7
+ 215	5
+ 782	6
+ 871	2
+ 31	5
+ 784	8
+ 509	7
+ 499	2
+ 17	3
+ 299	3
+ 250	8
+ 89	6
+ 130	3
+ 421	10
+ 104	8
+ 59	9
+ 543	3
+ 348	3
+ 824	2
+ 508	9
+ 717	3
+ 620	2
+ 950	1
+ 390	10
+ 448	7
+ 282	7
+ 457	4
+ 262	6
+ 716	7
+ 546	8
+ 496	6
+ 697	0
+ 879	0
+ 363	7
+ 265	9
+ 557	10
+ 163	2
+ 209	1
+ 296	6
+ 80	7
+ 288	4
+ 442	7
+ 733	7
+ 332	4
+ 387	9
+ 269	9
+ 483	10
+ 921	4
+ 12	3
+ 64	3
+ 155	6
+ 260	3
+ 799	5
+ 431	1
+ 68	5
+ 839	4
+ 873	3
+ 101	6
+ 986	4
+ 55	4
+ 311	3
+ 255	8
+ 290	2
+ 155	3
+ 460	2
+ 579	6
+ 840	8
+ 933	6
+ 308	4
+ 735	4
+ 875	6
+ 733	7
+ 855	8
+ 353	8
+ 268	4
+ 213	6
+ 732	5
+ 372	0
+ 644	5
+ 324	1
+ 746	9
+ 718	6
+ 743	7
+ 225	1
+ 15	10
+ 428	9
+ 534	2
+ 637	4
+ 996	10
+ 230	3
+ 399	4
+ 842	1
+ 911	2
+ 153	6
+ 741	5
+ 658	5
+ 380	4
+ 72	1
+ 28	3
+ 174	0
+ 258	6
+ 933	8
+ 763	6
+ 181	8
+ 561	4
+ 22	10
+ 854	9
+ 90	8
+ 78	2
+ 320	8
+ 719	10
+ 305	1
+ 354	4
+ 222	4
+ 675	4
+ 425	9
+ 997	4
+ 725	8
+ 928	9
+ 518	5
+ 317	5
+ 447	2
+ 405	5
+ 936	5
+ 780	3
+ 302	5
+ 233	6
+ 598	6
+ 985	8
+ 969	7
+ 215	4
+ 594	2
+ 752	3
+ 973	7
+ 224	5
+ 167	5
+ 32	6
+ 712	4
+ 152	6
+ 920	9
+ 903	2
+ 430	1
+ 830	0
+ 724	8
+ 848	7
+ 477	1
+ 88	1
+ 276	8
+ 389	2
+ 519	6
+ 740	7
+ 154	8
+ 301	9
+ 209	5
+ 514	1
+ 385	4
+ 351	8
+ 553	2
+ 843	3
+ 998	7
+ 971	5
+ 754	1
+ 545	0
+ 898	9
+ 279	4
+ 547	0
+ 104	7
+ 791	4
+ 568	10
+ 858	1
+ 129	2
+ 499	5
+ 58	1
+ 662	9
+ 330	7
+ 592	3
+ 134	3
+ 359	7
+ 376	3
+ 613	7
+ 675	2
+ 674	8
+ 862	5
+ 183	4
+ 465	0
+ 512	6
+ 284	0
+ 74	3
+ 63	7
+ 244	4
+ 395	8
+ 693	5
+ 181	1
+ 208	6
+ 309	8
+ 212	10
+ 981	9
+ 763	8
+ 352	9
+ 273	8
+ 988	8
+ 410	3
+ 796	5
+ 614	9
+ 220	9
+ 251	6
+ 693	9
+ 144	9
+ 995	4
+ 432	3
+ 174	6
+ 289	2
+ 531	1
+ 998	9
+ 997	3
+ 700	10
+ 57	1
+ 257	9
+ 594	9
+ 711	8
+ 730	10
+ 429	4
+ 905	6
+ 298	9
+ 926	7
+ 205	1
+ 374	5
+ 254	9
+ 545	3
+ 788	5
+ 524	5
+ 528	6
+ 598	8
+ 433	2
+ 656	1
+ 6	4
+ 105	4
+ 809	0
+ 8	1
+ 910	9
+ 836	1
+ 34	2
+ 608	3
+ 115	2
+ 541	9
+ 696	1
+ 391	2
+ 645	10
+ 8	1
+ 180	7
+ 220	2
+ 51	3
+ 621	9
+ 335	6
+ 966	2
+ 564	8
+ 359	6
+ 12	10
+ 887	1
+ 120	4
+ 31	8
+ 492	4
+ 40	1
+ 410	0
+ 213	6
+ 713	4
+ 777	8
+ 759	4
+ 623	1
+ 28	6
+ 338	6
+ 390	7
+ 191	4
+ 663	1
+ 530	8
+ 505	6
+ 599	10
+ 983	6
+ 133	4
+ 687	3
+ 984	4
+ 780	8
+ 163	5
+ 160	8
+ 632	2
+ 374	10
+ 780	8
+ 666	10
+ 167	3
+ 48	7
+ 112	6
+ 258	7
+ 549	2
+ 350	7
+ 635	0
+ 27	6
+ 437	8
+ 380	6
+ 345	5
+ 386	10
+ 727	8
+ 947	5
+ 525	6
+ 477	7
+ 942	5
+ 389	1
+ 77	6
+ 765	6
+ 889	1
+ 308	5
+ 153	3
+ 142	6
+ 143	5
+ 191	5
+ 62	6
+ 465	8
+ 338	4
+ 296	9
+ 25	8
+ 555	10
+ 298	9
+ 20	4
+ 591	8
+ 2	5
+ 901	3
+ 3	1
+ 645	1
+ 645	8
+ 667	8
+ 276	7
+ 413	7
+ 517	8
+ 153	8
+ 613	2
+ 586	2
+ 144	9
+ 112	2
+ 259	7
+ 949	3
+ 183	9
+ 570	2
+ 904	2
+ 331	5
+ 3	10
+ 385	3
+ 726	8
+ 20	2
+ 549	2
+ 56	2
+ 351	6
+ 330	5
+ 525	4
+ 658	8
+ 144	6
+ 45	3
+ 458	6
+ 513	4
+ 830	8
+ 911	8
+ 841	3
+ 112	6
+ 94	1
+ 810	6
+ 305	9
+ 806	7
+ 508	1
+ 150	0
+ 577	8
+ 817	7
+ 416	9
+ 49	9
+ 477	6
+ 236	3
+ 405	1
+ 140	2
+ 443	3
+ 812	5
+ 385	6
+ 181	7
+ 489	10
+ 345	10
+ 122	5
+ 30	7
+ 304	8
+ 421	7
+ 710	5
+ 594	2
+ 31	8
+ 493	4
+ 977	6
+ 681	4
+ 886	5
+ 958	3
+ 116	1
+ 960	6
+ 126	3
+ 602	2
+ 801	6
+ 948	1
+ 480	4
+ 825	2
+ 840	4
+ 376	9
+ 249	9
+ 307	2
+ 504	10
+ 646	4
+ 482	6
+ 661	6
+ 744	6
+ 203	9
+ 927	8
+ 118	7
+ 438	1
+ 833	9
+ 436	7
+ 108	3
+ 77	5
+ 147	3
+ 354	5
+ 552	9
+ 443	2
+ 248	9
+ 802	9
+ 523	5
+ 530	7
+ 416	5
+ 532	5
+ 186	10
+ 600	0
+ 887	0
+ 677	10
+ 312	8
+ 479	5
+ 80	8
+ 913	6
+ 691	4
+ 830	9
+ 281	6
+ 848	8
+ 178	4
+ 530	6
+ 835	1
+ 128	0
+ 31	7
+ 39	9
+ 765	7
+ 914	1
+ 470	4
+ 537	6
+ 226	4
+ 183	9
+ 806	0
+ 855	1
+ 645	7
+ 890	8
+ 81	4
+ 418	9
+ 482	5
+ 937	5
+ 274	10
+ 432	0
+ 692	3
+ 116	2
+ 738	7
+ 713	10
+ 102	9
+ 881	9
+ 909	7
+ 994	6
+ 439	9
+ 378	5
+ 304	8
+ 436	8
+ 341	4
+ 299	6
+ 349	7
+ 653	0
+ 76	8
+ 203	8
+ 421	9
+ 778	5
+ 812	7
+ 431	7
+ 395	4
+ 275	8
+ 309	7
+ 354	6
+ 449	8
+ 398	8
+ 163	7
+ 405	5
+ 428	1
+ 552	5
+ 828	8
+ 319	2
+ 672	1
+ 772	5
+ 756	2
+ 205	2
+ 628	5
+ 986	9
+ 134	3
+ 550	6
+ 130	9
+ 373	3
+ 644	8
+ 805	1
+ 837	4
+ 576	7
+ 113	9
+ 913	8
+ 992	7
+ 270	7
+ 889	5
+ 899	5
+ 956	9
+ 455	1
+ 225	0
+ 673	4
+ 952	0
+ 648	6
+ 825	5
+ 669	7
+ 811	2
+ 326	9
+ 140	2
+ 710	1
+ 925	10
+ 881	8
+ 454	8
+ 331	4
+ 665	8
+ 500	9
+ 791	2
+ 245	7
+ 219	9
+ 339	0
+ 347	0
+ 705	2
+ 253	0
+ 82	4
+ 270	8
+ 526	2
+ 771	4
+ 8	2
+ 186	3
+ 635	9
+ 126	1
+ 741	9
+ 307	10
+ 659	5
+ 878	10
+ 570	2
+ 5	3
+ 383	3
+ 306	5
+ 651	6
+ 256	2
+ 769	0
+ 583	8
+ 251	8
+ 117	9
+ 620	2
+ 21	4
+ 158	3
+ 346	8
+ 854	2
+ 814	4
+ 449	8
+ 699	8
+ 78	0
+ 296	7
+ 580	6
+ 905	3
+ 578	5
+ 127	8
+ 257	2
+ 715	9
+ 486	7
+ 237	6
+ 64	6
+ 461	9
+ 808	3
+ 342	3
+ 95	0
+ 89	2
+ 47	4
+ 901	6
+ 937	8
+ 977	5
+ 294	1
+ 344	6
+ 348	1
+ 428	8
+ 795	7
+ 478	9
+ 249	9
+ 777	1
+ 215	1
+ 314	3
+ 161	4
+ 482	2
+ 787	4
+ 835	7
+ 190	8
+ 238	5
+ 917	6
+ 36	3
+ 641	5
+ 100	4
+ 130	6
+ 295	4
+ 517	1
+ 436	7
+ 191	7
+ 42	4
+ 152	5
+ 559	9
+ 908	4
+ 663	1
+ 207	9
+ 583	1
+ 483	6
+ 390	1
+ 84	5
+ 561	2
+ 67	9
+ 593	6
+ 928	0
+ 316	1
+ 780	4
+ 470	9
+ 882	0
+ 871	8
+ 424	5
+ 888	6
+ 434	5
+ 756	9
+ 90	1
+ 42	2
+ 636	6
+ 387	7
+ 459	10
+ 288	4
+ 11	6
+ 505	8
+ 962	10
+ 722	8
+ 4	6
+ 634	4
+ 125	5
+ 59	6
+ 994	8
+ 476	1
+ 962	5
+ 257	6
+ 121	6
+ 301	6
+ 625	6
+ 966	6
+ 193	5
+ 426	2
+ 445	1
+ 1000	4
+ 739	6
+ 876	9
+ 157	9
+ 424	2
+ 751	9
+ 234	7
+ 418	5
+ 310	5
+ 135	6
+ 118	8
+ 200	1
+ 396	4
+ 555	8
+ 548	0
+ 969	5
+ 449	7
+ 183	3
+ 572	3
+ 261	10
+ 490	0
+ 896	7
+ 724	3
+ 214	0
+ 853	3
+ 645	10
+ 109	8
+ 56	5
+ 237	6
+ 326	8
+ 611	3
+ 334	1
+ 3	5
+ 385	6
+ 856	6
+ 571	3
+ 658	5
+ 69	4
+ 782	3
+ 415	6
+ 633	1
+ 607	7
+ 904	7
+ 248	1
+ 274	6
+ 927	9
+ 869	3
+ 945	9
+ 777	3
+ 447	6
+ 977	0
+ 978	6
+ 485	0
+ 16	3
+ 331	4
+ 902	10
+ 491	5
+ 707	4
+ 172	10
+ 537	4
+ 528	5
+ 331	4
+ 724	3
+ 268	5
+ 607	7
+ 134	6
+ 733	1
+ 219	2
+ 159	2
+ 485	5
+ 666	4
+ 455	2
+ 897	2
+ 552	1
+ 116	1
+ 515	6
+ 552	8
+ 42	3
+ 123	3
+ 777	7
+ 25	9
+ 314	8
+ 23	5
+ 975	2
+ 767	5
+ 673	4
+ 849	1
+ 591	7
+ 290	1
+ 815	4
+ 232	3
+ 51	8
+ 176	1
+ 61	3
+ 403	8
+ 28	4
+ 748	3
+ 185	8
+ 875	2
+ 953	6
+ 621	6
+ 76	5
+ 754	7
+ 216	0
+ 810	0
+ 451	0
+ 360	5
+ 826	5
+ 596	9
+ 834	10
+ 724	9
+ 426	5
+ 205	6
+ 244	1
+ 771	2
+ 724	4
+ 823	8
+ 863	6
+ 466	1
+ 622	3
+ 109	1
+ 318	5
+ 576	1
+ 6	2
+ 30	8
+ 170	8
+ 702	6
+ 226	9
+ 207	5
+ 989	10
+ 667	7
+ 372	5
+ 512	2
+ 67	10
+ 313	7
+ 254	4
+ 762	6
+ 892	3
+ 715	9
+ 510	7
+ 738	7
+ 498	4
+ 276	7
+ 348	5
+ 194	3
+ 462	9
+ 49	8
+ 350	6
+ 68	4
+ 539	4
+ 106	8
+ 804	9
+ 365	7
+ 207	1
+ 595	7
+ 824	3
+ 397	3
+ 773	7
+ 47	1
+ 156	2
+ 457	6
+ 101	5
+ 452	5
+ 66	5
+ 869	6
+ 902	10
+ 397	7
+ 844	8
+ 403	1
+ 841	10
+ 768	7
+ 330	2
+ 988	1
+ 837	0
+ 223	10
+ 276	7
+ 611	4
+ 185	1
+ 829	3
+ 583	7
+ 855	5
+ 672	3
+ 190	5
+ 14	6
+ 567	9
+ 590	3
+ 521	9
+ 498	5
+ 22	3
+ 544	2
+ 328	8
+ 925	9
+ 197	1
+ 1	0
+ 361	6
+ 723	2
+ 68	4
+ 469	3
+ 911	5
+ 851	5
+ 338	4
+ 812	9
+ 361	3
+ 368	4
+ 645	9
+ 629	10
+ 732	6
+ 911	9
+ 663	9
+ 955	0
+ 495	7
+ 241	6
+ 74	7
+ 820	10
+ 192	7
+ 462	5
+ 112	3
+ 388	5
+ 584	8
+ 856	2
+ 667	5
+ 201	4
+ 38	1
+ 329	7
+ 24	3
+ 726	5
+ 963	10
+ 81	0
+ 676	9
+ 21	9
+ 573	5
+ 398	7
+ 757	8
+ 157	3
+ 542	0
+ 569	2
+ 498	8
+ 608	5
+ 882	9
+ 238	9
+ 221	10
+ 424	2
+ 931	5
+ 221	6
+ 407	2
+ 476	10
+ 725	9
+ 664	5
+ 660	8
+ 822	2
+ 835	4
+ 411	3
+ 160	0
+ 870	0
+ 956	1
+ 947	2
+ 73	4
+ 362	0
+ 877	6
+ 612	3
+ 824	1
+ 265	5
+ 963	9
+ 31	6
+ 751	9
+ 825	6
+ 243	2
+ 920	4
+ 256	8
+ 445	2
+ 898	4
+ 390	10
+ 764	8
+ 975	6
+ 335	6
+ 926	2
+ 675	2
+ 708	6
+ 121	7
+ 261	9
+ 592	1
+ 458	8
+ 323	4
+ 238	6
+ 167	7
+ 791	1
+ 75	2
+ 36	8
+ 933	0
+ 481	3
+ 597	4
+ 427	3
+ 598	1
+ 910	7
+ 874	2
+ 590	5
+ 258	0
+ 300	6
+ 425	5
+ 160	6
+ 221	10
+ 657	3
+ 131	7
+ 134	1
+ 703	6
+ 332	3
+ 22	8
+ 573	6
+ 894	5
+ 339	8
+ 655	9
+ 234	9
+ 978	5
+ 494	4
+ 73	7
+ 995	3
+ 603	7
+ 588	7
+ 345	7
+ 799	0
+ 338	1
+ 349	4
+ 889	9
+ 980	8
+ 404	3
+ 551	1
+ 249	8
+ 972	2
+ 319	5
+ 629	4
+ 118	6
+ 685	7
+ 277	3
+ 456	6
+ 996	3
+ 670	3
+ 385	0
+ 694	3
+ 940	7
+ 57	3
+ 993	6
+ 404	2
+ 392	4
+ 468	7
+ 840	1
+ 103	10
+ 721	8
+ 680	10
+ 61	1
+ 620	1
+ 392	3
+ 391	8
+ 310	1
+ 51	3
+ 759	1
+ 595	8
+ 716	10
+ 993	1
+ 374	5
+ 819	2
+ 558	9
+ 172	3
+ 710	9
+ 278	8
+ 989	9
+ 829	4
+ 188	2
+ 158	5
+ 305	2
+ 748	1
+ 317	3
+ 815	0
+ 341	8
+ 141	7
+ 270	10
+ 929	8
+ 883	1
+ 108	6
+ 954	4
+ 364	9
+ 283	2
+ 324	5
+ 413	5
+ 970	7
+ 691	7
+ 781	0
+ 61	6
+ 41	4
+ 405	2
+ 118	7
+ 142	0
+ 504	0
+ 148	6
+ 618	1
+ 997	10
+ 46	3
+ 175	4
+ 752	6
+ 852	7
+ 306	5
+ 440	1
+ 552	5
+ 684	6
+ 904	1
+ 775	0
+ 764	9
+ 68	3
+ 942	2
+ 880	6
+ 319	9
+ 542	4
+ 157	7
+ 734	9
+ 306	6
+ 632	6
+ 130	1
+ 699	7
+ 574	4
+ 275	5
+ 472	1
+ 500	2
+ 968	6
+ 505	9
+ 785	4
+ 470	1
+ 261	0
+ 468	4
+ 730	2
+ 328	0
+ 788	10
+ 648	9
+ 32	3
+ 601	6
+ 730	9
+ 83	2
+ 926	6
+ 439	9
+ 151	9
+ 803	9
+ 327	3
+ 39	6
+ 285	5
+ 7	0
+ 709	3
+ 52	5
+ 294	7
+ 416	3
+ 47	0
+ 931	8
+ 892	0
+ 979	8
+ 597	4
+ 712	7
+ 361	5
+ 685	7
+ 789	7
+ 277	1
+ 231	3
+ 89	9
+ 618	1
+ 437	9
+ 840	9
+ 237	9
+ 869	2
+ 664	8
+ 181	6
+ 580	8
+ 61	3
+ 527	4
+ 808	2
+ 110	6
+ 936	4
+ 671	2
+ 670	8
+ 106	3
+ 901	5
+ 199	7
+ 395	4
+ 629	3
+ 603	3
+ 26	8
+ 936	6
+ 562	10
+ 898	1
+ 418	7
+ 301	5
+ 303	2
+ 915	10
+ 403	6
+ 733	5
+ 873	6
+ 52	1
+ 376	4
+ 508	0
+ 712	1
+ 297	7
+ 894	2
+ 344	5
+ 229	2
+ 546	6
+ 948	8
+ 176	3
+ 84	1
+ 225	5
+ 677	10
+ 996	5
+ 592	0
+ 622	10
+ 495	1
+ 972	2
+ 240	3
+ 944	1
+ 502	3
+ 591	7
+ 530	1
+ 379	5
+ 984	6
+ 730	1
+ 646	10
+ 555	3
+ 912	6
+ 873	5
+ 598	5
+ 472	1
+ 625	4
+ 299	9
+ 713	2
+ 1000	2
+ 531	6
+ 946	1
+ 728	3
+ 540	7
+ 881	3
+ 781	5
+ 223	3
+ 850	1
+ 885	7
+ 639	5
+ 218	1
+ 576	8
+ 555	9
+ 707	3
+ 120	7
+ 483	7
+ 298	4
+ 712	0
+ 755	3
+ 739	6
+ 521	5
+ 162	7
+ 854	0
+ 880	7
+ 735	5
+ 223	10
+ 630	8
+ 795	2
+ 676	5
+ 454	8
+ 208	9
+ 446	5
+ 367	2
+ 532	1
+ 410	3
+ 757	9
+ 789	9
+ 676	6
+ 931	6
+ 384	7
+ 74	6
+ 618	7
+ 407	4
+ 890	1
+ 915	3
+ 878	1
+ 281	3
+ 629	6
+ 482	2
+ 769	9
+ 431	5
+ 824	2
+ 445	5
+ 865	4
+ 55	2
+ 42	1
+ 855	7
+ 834	3
+ 73	7
+ 344	10
+ 68	2
+ 111	3
+ 545	7
+ 996	0
+ 901	8
+ 920	3
+ 291	7
+ 553	7
+ 243	4
+ 111	3
+ 666	2
+ 427	5
+ 812	3
+ 783	9
+ 985	1
+ 873	1
+ 348	10
+ 401	9
+ 724	4
+ 921	6
+ 163	8
+ 957	5
+ 584	5
+ 189	8
+ 928	3
+ 125	6
+ 452	6
+ 114	3
+ 814	9
+ 150	8
+ 23	0
+ 851	4
+ 7	3
+ 265	7
+ 650	2
+ 356	8
+ 25	3
+ 266	6
+ 824	5
+ 436	8
+ 754	6
+ 345	2
+ 114	5
+ 471	9
+ 356	6
+ 726	4
+ 644	6
+ 751	7
+ 829	0
+ 383	5
+ 201	7
+ 291	2
+ 53	6
+ 836	9
+ 11	3
+ 628	8
+ 834	10
+ 972	9
+ 433	4
+ 875	8
+ 63	6
+ 170	7
+ 178	9
+ 359	0
+ 937	7
+ 487	1
+ 481	8
+ 365	5
+ 335	2
+ 411	3
+ 472	0
+ 112	3
+ 13	1
+ 254	4
+ 526	1
+ 236	6
+ 730	4
+ 297	9
+ 327	7
+ 916	3
+ 399	4
+ 402	9
+ 181	8
+ 414	5
+ 967	8
+ 862	4
+ 865	10
+ 745	9
+ 58	10
+ 325	6
+ 128	6
+ 173	9
+ 967	5
+ 767	3
+ 127	7
+ 558	5
+ 86	10
+ 405	3
+ 726	8
+ 783	7
+ 645	6
+ 132	5
+ 619	9
+ 388	7
+ 876	7
+ 260	0
+ 273	4
+ 862	2
+ 903	6
+ 534	0
+ 312	1
+ 555	4
+ 51	10
+ 665	8
+ 780	4
+ 469	4
+ 93	6
+ 934	7
+ 477	3
+ 388	4
+ 34	6
+ 356	3
+ 81	2
+ 546	10
+ 847	1
+ 15	2
+ 171	6
+ 558	2
+ 531	2
+ 998	3
+ 672	5
+ 735	8
+ 67	7
+ 476	5
+ 991	9
+ 897	0
+ 512	3
+ 332	6
+ 471	9
+ 578	3
+ 958	6
+ 477	1
+ 163	0
+ 351	7
+ 259	3
+ 4	9
+ 816	7
+ 695	9
+ 409	2
+ 427	4
+ 35	3
+ 426	5
+ 576	8
+ 140	0
+ 636	7
+ 365	6
+ 311	8
+ 724	5
+ 877	1
+ 167	1
+ 424	2
+ 67	2
+ 911	8
+ 122	3
+ 932	5
+ 721	10
+ 872	1
+ 514	4
+ 905	7
+ 495	5
+ 372	9
+ 135	7
+ 702	9
+ 156	6
+ 933	3
+ 715	4
+ 495	8
+ 596	4
+ 543	7
+ 726	5
+ 267	4
+ 442	1
+ 595	10
+ 588	5
+ 610	1
+ 40	10
+ 943	2
+ 665	6
+ 34	8
+ 224	10
+ 145	9
+ 324	6
+ 721	9
+ 45	3
+ 638	8
+ 739	9
+ 219	2
+ 45	8
+ 138	6
+ 314	7
+ 717	4
+ 730	7
+ 529	4
+ 305	6
+ 216	5
+ 531	4
+ 468	9
+ 0	2
+ 776	0
+ 453	4
+ 817	2
+ 320	0
+ 373	4
+ 850	5
+ 998	2
+ 259	7
+ 518	10
+ 375	0
+ 384	7
+ 611	6
+ 209	1
+ 961	7
+ 998	10
+ 866	8
+ 7	3
+ 188	8
+ 511	5
+ 861	9
+ 873	7
+ 395	9
+ 875	7
+ 586	4
+ 643	10
+ 441	0
+ 642	1
+ 628	9
+ 195	6
+ 529	2
+ 551	4
+ 967	6
+ 714	2
+ 383	2
+ 663	2
+ 109	5
+ 955	5
+ 408	8
+ 158	10
+ 223	8
+ 956	7
+ 829	6
+ 717	5
+ 449	9
+ 46	10
+ 104	6
+ 373	1
+ 156	1
+ 226	5
+ 313	9
+ 781	4
+ 426	7
+ 926	8
+ 566	1
+ 830	8
+ 886	8
+ 454	7
+ 384	2
+ 172	8
+ 82	2
+ 811	2
+ 816	2
+ 257	10
+ 272	5
+ 509	6
+ 373	3
+ 6	8
+ 27	9
+ 635	6
+ 16	5
+ 382	9
+ 250	8
+ 617	6
+ 7	8
+ 468	1
+ 7	3
+ 275	8
+ 464	5
+ 794	7
+ 16	3
+ 320	4
+ 593	3
+ 189	6
+ 259	8
+ 213	3
+ 288	6
+ 177	5
+ 431	8
+ 173	4
+ 583	6
+ 527	6
+ 920	8
+ 413	4
+ 335	2
+ 120	4
+ 509	4
+ 740	1
+ 767	9
+ 722	0
+ 754	9
+ 301	0
+ 530	5
+ 581	10
+ 273	8
+ 400	9
+ 395	9
+ 446	3
+ 728	9
+ 700	1
+ 65	8
+ 414	6
+ 260	2
+ 676	0
+ 84	4
+ 52	8
+ 334	4
+ 880	9
+ 832	5
+ 826	1
+ 216	2
+ 960	6
+ 152	4
+ 927	9
+ 265	6
+ 943	3
+ 446	4
+ 904	7
+ 511	6
+ 733	6
+ 979	8
+ 433	3
+ 138	3
+ 177	10
+ 775	0
+ 74	10
+ 227	0
+ 603	4
+ 441	5
+ 259	7
+ 157	2
+ 37	6
+ 559	9
+ 309	1
+ 522	0
+ 666	5
+ 827	1
+ 814	10
+ 413	10
+ 935	2
+ 993	0
+ 180	2
+ 44	8
+ 599	5
+ 312	9
+ 191	5
+ 61	2
+ 73	6
+ 169	4
+ 691	7
+ 424	4
+ 192	3
+ 456	0
+ 217	9
+ 997	2
+ 57	10
+ 162	2
+ 210	2
+ 19	8
+ 690	3
+ 668	9
+ 801	7
+ 109	9
+ 350	3
+ 256	0
+ 969	7
+ 399	2
+ 932	9
+ 168	1
+ 724	2
+ 301	8
+ 154	5
+ 19	4
+ 668	0
+ 173	4
+ 370	8
+ 239	2
+ 570	3
+ 45	9
+ 626	3
+ 962	6
+ 982	4
+ 757	9
+ 216	9
+ 63	9
+ 89	4
+ 722	2
+ 828	7
+ 606	5
+ 779	8
+ 854	1
+ 619	1
+ 320	2
+ 441	4
+ 110	1
+ 666	1
+ 663	6
+ 432	4
+ 562	6
+ 344	6
+ 588	4
+ 989	3
+ 676	8
+ 51	3
+ 313	8
+ 61	2
+ 978	7
+ 260	3
+ 870	7
+ 663	10
+ 768	3
+ 50	4
+ 978	5
+ 850	5
+ 129	2
+ 165	7
+ 628	2
+ 27	3
+ 971	1
+ 586	3
+ 907	6
+ 450	9
+ 327	7
+ 184	2
+ 410	8
+ 175	2
+ 177	2
+ 608	2
+ 707	5
+ 694	8
+ 652	9
+ 554	3
+ 13	6
+ 584	10
+ 658	2
+ 267	6
+ 816	7
+ 450	1
+ 428	6
+ 339	8
+ 480	5
+ 16	7
+ 739	6
+ 811	4
+ 82	5
+ 283	7
+ 364	8
+ 15	4
+ 417	6
+ 360	1
+ 769	6
+ 640	6
+ 345	1
+ 728	8
+ 723	1
+ 611	2
+ 581	6
+ 861	3
+ 252	7
+ 767	3
+ 177	1
+ 69	5
+ 887	1
+ 918	3
+ 684	3
+ 380	5
+ 906	0
+ 38	3
+ 110	8
+ 24	8
+ 833	6
+ 37	4
+ 263	9
+ 733	5
+ 570	5
+ 849	7
+ 550	9
+ 288	4
+ 2	2
+ 742	7
+ 484	1
+ 139	4
+ 142	2
+ 640	3
+ 942	7
+ 85	8
+ 300	1
+ 188	6
+ 20	9
+ 76	6
+ 422	9
+ 336	10
+ 843	6
+ 409	8
+ 830	2
+ 531	3
+ 274	7
+ 704	4
+ 846	3
+ 667	8
+ 8	8
+ 564	3
+ 874	8
+ 870	9
+ 674	9
+ 483	1
+ 871	8
+ 68	7
+ 444	5
+ 559	3
+ 629	1
+ 588	9
+ 760	3
+ 318	6
+ 636	10
+ 395	6
+ 737	10
+ 951	6
+ 711	8
+ 505	4
+ 767	10
+ 480	6
+ 807	5
+ 353	3
+ 25	9
+ 525	7
+ 2	1
+ 555	8
+ 405	9
+ 369	0
+ 858	8
+ 684	6
+ 723	6
+ 207	4
+ 456	7
+ 818	2
+ 701	3
+ 862	5
+ 845	2
+ 759	9
+ 127	3
+ 523	1
+ 397	1
+ 892	8
+ 952	3
+ 841	8
+ 25	5
+ 406	7
+ 160	6
+ 181	6
+ 325	10
+ 840	0
+ 297	7
+ 534	1
+ 916	3
+ 13	0
+ 577	5
+ 172	10
+ 615	1
+ 775	6
+ 325	6
+ 377	3
+ 141	8
+ 97	3
+ 396	3
+ 918	7
+ 278	8
+ 747	6
+ 459	3
+ 717	4
+ 574	7
+ 418	2
+ 265	6
+ 125	9
+ 655	9
+ 447	10
+ 516	8
+ 329	7
+ 606	4
+ 959	0
+ 705	9
+ 723	10
+ 634	5
+ 557	1
+ 751	3
+ 468	3
+ 4	9
+ 477	3
+ 477	6
+ 149	1
+ 501	6
+ 111	0
+ 419	4
+ 674	0
+ 867	6
+ 28	6
+ 509	8
+ 554	1
+ 221	1
+ 236	10
+ 385	7
+ 298	4
+ 590	8
+ 657	1
+ 375	8
+ 200	9
+ 402	3
+ 893	8
+ 752	6
+ 847	6
+ 199	9
+ 190	7
+ 626	7
+ 852	8
+ 854	1
+ 819	2
+ 792	1
+ 627	4
+ 891	3
+ 450	3
+ 91	6
+ 142	5
+ 961	0
+ 315	7
+ 602	2
+ 331	8
+ 37	5
+ 510	7
+ 265	4
+ 509	1
+ 450	3
+ 358	2
+ 445	10
+ 624	3
+ 270	1
+ 602	4
+ 724	7
+ 854	7
+ 779	2
+ 397	4
+ 331	7
+ 182	4
+ 248	7
+ 31	5
+ 55	5
+ 632	5
+ 869	10
+ 746	3
+ 976	4
+ 649	2
+ 445	3
+ 606	2
+ 995	5
+ 853	8
+ 629	2
+ 155	10
+ 977	3
+ 329	2
+ 30	4
+ 738	1
+ 901	4
+ 589	8
+ 361	3
+ 84	3
+ 706	7
+ 582	2
+ 984	2
+ 319	10
+ 648	2
+ 753	3
+ 421	9
+ 237	4
+ 246	6
+ 623	3
+ 926	4
+ 361	8
+ 732	9
+ 597	1
+ 285	7
+ 430	10
+ 414	0
+ 141	4
+ 201	5
+ 378	8
+ 631	1
+ 126	1
+ 40	4
+ 449	3
+ 929	1
+ 562	9
+ 433	9
+ 682	2
+ 872	3
+ 258	2
+ 960	7
+ 147	4
+ 700	3
+ 773	9
+ 747	2
+ 749	4
+ 282	9
+ 429	3
+ 239	9
+ 608	2
+ 949	2
+ 23	4
+ 92	7
+ 546	10
+ 984	8
+ 121	9
+ 491	3
+ 318	2
+ 556	1
+ 91	3
+ 242	8
+ 680	5
+ 716	1
+ 846	10
+ 986	5
+ 123	9
+ 624	1
+ 317	7
+ 851	9
+ 681	8
+ 668	8
+ 778	2
+ 71	1
+ 350	6
+ 186	4
+ 929	4
+ 282	6
+ 952	10
+ 718	8
+ 952	7
+ 252	1
+ 639	9
+ 221	10
+ 593	1
+ 820	3
+ 906	5
+ 76	7
+ 647	1
+ 779	10
+ 774	10
+ 438	7
+ 393	7
+ 312	3
+ 718	0
+ 143	7
+ 734	4
+ 745	4
+ 271	10
+ 330	9
+ 37	1
+ 138	9
+ 637	2
+ 627	3
+ 361	4
+ 281	1
+ 372	7
+ 838	8
+ 440	1
+ 110	2
+ 180	3
+ 828	9
+ 647	6
+ 287	9
+ 538	6
+ 782	6
+ 766	9
+ 518	4
+ 133	1
+ 688	5
+ 551	10
+ 629	9
+ 689	5
+ 688	1
+ 616	8
+ 287	8
+ 50	1
+ 709	7
+ 687	10
+ 616	2
+ 613	4
+ 801	4
+ 316	3
+ 782	4
+ 464	5
+ 944	0
+ 439	6
+ 939	1
+ 39	6
+ 257	7
+ 425	5
+ 451	5
+ 658	2
+ 173	3
+ 157	8
+ 570	8
+ 186	4
+ 148	5
+ 690	9
+ 951	2
+ 400	9
+ 170	8
+ 468	1
+ 967	5
+ 735	2
+ 162	2
+ 768	6
+ 635	4
+ 774	8
+ 771	9
+ 596	3
+ 700	8
+ 712	8
+ 283	4
+ 778	2
+ 556	2
+ 129	7
+ 17	6
+ 834	10
+ 104	6
+ 208	3
+ 729	10
+ 879	4
+ 403	7
+ 171	2
+ 583	8
+ 516	3
+ 548	2
+ 131	8
+ 631	9
+ 66	2
+ 86	2
+ 912	1
+ 792	7
+ 86	9
+ 315	3
+ 161	0
+ 272	0
+ 408	7
+ 693	6
+ 850	3
+ 346	4
+ 559	9
+ 595	7
+ 726	2
+ 598	8
+ 412	7
+ 987	3
+ 786	8
+ 70	9
+ 676	4
+ 167	8
+ 430	4
+ 877	8
+ 113	6
+ 417	10
+ 846	8
+ 330	4
+ 657	9
+ 94	4
+ 150	7
+ 175	6
+ 376	2
+ 886	2
+ 942	10
+ 34	6
+ 342	2
+ 455	8
+ 639	3
+ 610	8
+ 902	0
+ 715	7
+ 789	0
+ 152	4
+ 969	2
+ 829	1
+ 938	0
+ 682	3
+ 166	6
+ 475	1
+ 525	5
+ 725	9
+ 709	2
+ 639	3
+ 511	2
+ 99	4
+ 275	8
+ 160	1
+ 859	3
+ 509	8
+ 558	3
+ 948	5
+ 341	6
+ 809	5
+ 198	3
+ 614	7
+ 792	3
+ 590	5
+ 519	2
+ 848	0
+ 478	9
+ 443	8
+ 761	6
+ 816	6
+ 916	3
+ 448	5
+ 663	4
+ 970	0
+ 26	8
+ 512	2
+ 62	1
+ 947	9
+ 465	5
+ 354	10
+ 766	2
+ 14	2
+ 149	5
+ 996	9
+ 61	8
+ 530	10
+ 138	10
+ 451	8
+ 374	4
+ 806	4
+ 199	3
+ 623	3
+ 443	6
+ 115	9
+ 107	5
+ 893	9
+ 671	9
+ 117	8
+ 365	1
+ 730	4
+ 926	3
+ 403	1
+ 237	9
+ 865	6
+ 275	7
+ 10	5
+ 988	6
+ 736	4
+ 204	9
+ 340	3
+ 321	2
+ 185	10
+ 140	3
+ 812	5
+ 416	5
+ 931	3
+ 802	3
+ 405	0
+ 189	3
+ 650	5
+ 941	7
+ 939	9
+ 295	7
+ 361	5
+ 526	7
+ 810	8
+ 934	10
+ 839	1
+ 297	7
+ 579	7
+ 194	5
+ 54	10
+ 845	5
+ 36	0
+ 730	7
+ 498	7
+ 346	4
+ 602	6
+ 112	10
+ 140	6
+ 665	9
+ 486	6
+ 945	3
+ 673	2
+ 977	3
+ 954	2
+ 763	0
+ 167	6
+ 468	2
+ 641	2
+ 888	1
+ 870	2
+ 576	5
+ 876	7
+ 434	0
+ 326	1
+ 965	8
+ 698	9
+ 136	4
+ 151	1
+ 624	1
+ 284	4
+ 114	5
+ 994	6
+ 654	6
+ 780	5
+ 773	7
+ 777	3
+ 122	7
+ 36	6
+ 669	4
+ 655	6
+ 174	4
+ 544	3
+ 724	7
+ 423	3
+ 801	7
+ 734	9
+ 158	7
+ 497	8
+ 362	3
+ 354	1
+ 928	1
+ 484	0
+ 784	5
+ 605	5
+ 882	3
+ 87	1
+ 613	6
+ 365	3
+ 326	8
+ 685	1
+ 495	4
+ 42	7
+ 148	5
+ 465	5
+ 816	8
+ 646	7
+ 950	1
+ 793	7
+ 649	4
+ 187	5
+ 658	3
+ 587	3
+ 904	10
+ 608	2
+ 740	3
+ 356	2
+ 712	4
+ 888	9
+ 937	4
+ 370	8
+ 172	0
+ 497	1
+ 146	3
+ 855	8
+ 687	0
+ 327	3
+ 315	9
+ 616	2
+ 866	2
+ 449	6
+ 516	8
+ 842	2
+ 203	7
+ 89	1
+ 83	5
+ 893	3
+ 475	4
+ 376	6
+ 679	2
+ 416	4
+ 272	7
+ 711	6
+ 656	3
+ 806	5
+ 550	3
+ 129	1
+ 60	10
+ 295	3
+ 701	4
+ 403	8
+ 843	3
+ 39	3
+ 686	4
+ 940	4
+ 645	4
+ 732	9
+ 99	4
+ 504	8
+ 770	3
+ 278	3
+ 565	4
+ 386	6
+ 377	7
+ 887	1
+ 65	3
+ 861	9
+ 586	9
+ 227	3
+ 315	2
+ 638	10
+ 523	4
+ 878	6
+ 812	4
+ 378	6
+ 693	7
+ 901	3
+ 62	3
+ 881	4
+ 968	8
+ 517	0
+ 58	4
+ 941	6
+ 278	2
+ 917	6
+ 335	6
+ 553	9
+ 923	4
+ 480	7
+ 813	9
+ 316	5
+ 514	2
+ 763	6
+ 504	6
+ 16	5
+ 413	5
+ 505	5
+ 911	4
+ 116	2
+ 614	0
+ 782	9
+ 587	3
+ 806	5
+ 767	3
+ 246	6
+ 145	6
+ 86	7
+ 780	8
+ 236	3
+ 494	3
+ 756	9
+ 785	3
+ 378	7
+ 707	5
+ 885	3
+ 527	7
+ 269	1
+ 4	1
+ 625	8
+ 362	9
+ 351	5
+ 433	4
+ 166	2
+ 287	4
+ 497	8
+ 655	3
+ 688	4
+ 514	1
+ 137	2
+ 561	0
+ 541	1
+ 690	8
+ 202	7
+ 885	8
+ 464	2
+ 698	8
+ 753	1
+ 252	9
+ 345	5
+ 322	8
+ 321	10
+ 95	0
+ 418	6
+ 76	6
+ 829	6
+ 576	4
+ 725	3
+ 180	9
+ 959	1
+ 755	4
+ 311	5
+ 238	1
+ 585	5
+ 983	9
+ 30	3
+ 772	4
+ 283	9
+ 360	7
+ 476	4
+ 256	3
+ 73	8
+ 675	8
+ 98	9
+ 726	1
+ 919	5
+ 480	2
+ 934	7
+ 293	5
+ 208	3
+ 450	2
+ 582	2
+ 588	9
+ 88	9
+ 567	6
+ 384	8
+ 869	5
+ 655	5
+ 255	8
+ 398	10
+ 810	3
+ 461	3
+ 546	4
+ 8	8
+ 915	2
+ 115	4
+ 453	7
+ 586	0
+ 562	7
+ 988	1
+ 238	4
+ 952	1
+ 829	6
+ 650	1
+ 359	0
+ 64	2
+ 365	5
+ 459	9
+ 920	5
+ 749	8
+ 683	9
+ 200	1
+ 561	8
+ 176	1
+ 460	2
+ 252	7
+ 537	2
+ 805	4
+ 810	5
+ 449	2
+ 503	5
+ 338	9
+ 37	8
+ 778	10
+ 264	5
+ 793	9
+ 390	10
+ 83	10
+ 778	3
+ 74	2
+ 424	3
+ 936	10
+ 530	7
+ 326	3
+ 196	8
+ 509	7
+ 287	8
+ 567	3
+ 645	3
+ 282	9
+ 871	1
+ 856	3
+ 68	9
+ 212	8
+ 198	3
+ 84	6
+ 613	0
+ 583	1
+ 761	9
+ 484	10
+ 684	10
+ 657	10
+ 841	2
+ 296	5
+ 569	6
+ 395	4
+ 653	3
+ 702	7
+ 190	9
+ 567	4
+ 201	7
+ 11	8
+ 670	6
+ 957	4
+ 504	4
+ 389	2
+ 435	0
+ 160	3
+ 270	5
+ 761	8
+ 34	2
+ 279	7
+ 407	10
+ 408	6
+ 894	10
+ 986	1
+ 625	10
+ 908	3
+ 592	9
+ 727	1
+ 307	1
+ 285	7
+ 162	4
+ 17	4
+ 900	8
+ 270	9
+ 934	5
+ 622	3
+ 529	0
+ 939	4
+ 5	9
+ 518	6
+ 923	4
+ 925	5
+ 292	7
+ 612	6
+ 768	9
+ 341	9
+ 341	4
+ 362	2
+ 136	6
+ 175	1
+ 181	8
+ 411	7
+ 826	4
+ 134	8
+ 275	7
+ 461	2
+ 79	4
+ 714	4
+ 38	3
+ 970	8
+ 222	3
+ 737	6
+ 668	1
+ 803	8
+ 732	10
+ 873	9
+ 774	3
+ 623	6
+ 635	8
+ 431	9
+ 409	9
+ 108	5
+ 278	8
+ 858	3
+ 147	8
+ 123	4
+ 139	9
+ 931	8
+ 959	7
+ 611	7
+ 712	5
+ 604	5
+ 769	2
+ 86	4
+ 985	5
+ 313	4
+ 408	4
+ 881	7
+ 243	7
+ 2	4
+ 568	1
+ 760	7
+ 985	7
+ 514	9
+ 426	1
+ 636	1
+ 608	2
+ 624	4
+ 467	7
+ 780	5
+ 227	1
+ 846	6
+ 514	7
+ 321	8
+ 467	3
+ 148	0
+ 448	9
+ 742	4
+ 598	3
+ 378	0
+ 380	0
+ 162	10
+ 253	8
+ 365	7
+ 495	1
+ 173	7
+ 238	0
+ 356	8
+ 746	7
+ 510	2
+ 0	7
+ 248	4
+ 565	10
+ 882	2
+ 246	3
+ 187	6
+ 272	3
+ 614	5
+ 134	10
+ 246	6
+ 125	4
+ 350	4
+ 437	7
+ 115	2
+ 384	6
+ 396	4
+ 282	6
+ 833	8
+ 634	7
+ 10	9
+ 973	2
+ 507	2
+ 545	1
+ 771	7
+ 100	0
+ 307	2
+ 435	7
+ 588	9
+ 364	7
+ 55	7
+ 327	5
+ 132	6
+ 95	10
+ 455	7
+ 679	5
+ 609	7
+ 661	1
+ 897	2
+ 237	7
+ 885	3
+ 685	2
+ 563	1
+ 849	2
+ 991	2
+ 853	0
+ 961	2
+ 497	1
+ 788	6
+ 57	2
+ 320	7
+ 708	9
+ 387	4
+ 46	3
+ 575	3
+ 953	5
+ 620	6
+ 652	2
+ 758	5
+ 333	7
+ 714	2
+ 795	7
+ 365	3
+ 767	2
+ 883	8
+ 396	2
+ 559	1
+ 133	9
+ 472	2
+ 232	0
+ 461	2
+ 507	1
+ 823	2
+ 264	6
+ 659	6
+ 329	4
+ 783	1
+ 47	1
+ 416	8
+ 300	3
+ 638	7
+ 502	2
+ 800	6
+ 145	3
+ 814	4
+ 319	3
+ 561	8
+ 356	4
+ 984	6
+ 964	6
+ 218	3
+ 16	0
+ 418	1
+ 148	8
+ 878	4
+ 133	5
+ 144	6
+ 714	9
+ 270	9
+ 217	1
+ 235	5
+ 358	8
+ 362	7
+ 180	3
+ 335	1
+ 989	6
+ 437	0
+ 553	9
+ 69	7
+ 689	9
+ 149	8
+ 463	3
+ 457	2
+ 238	7
+ 36	5
+ 810	3
+ 990	2
+ 67	4
+ 883	2
+ 698	2
+ 390	7
+ 771	8
+ 693	3
+ 683	8
+ 26	4
+ 709	2
+ 194	2
+ 469	7
+ 349	7
+ 377	4
+ 161	2
+ 656	2
+ 355	7
+ 503	2
+ 969	2
+ 456	4
+ 889	2
+ 187	6
+ 553	9
+ 344	6
+ 241	1
+ 754	4
+ 225	2
+ 85	6
+ 929	5
+ 960	1
+ 650	6
+ 241	0
+ 339	7
+ 244	3
+ 946	7
+ 668	8
+ 928	9
+ 418	5
+ 725	8
+ 59	10
+ 815	8
+ 400	0
+ 35	5
+ 614	10
+ 948	6
+ 53	6
+ 190	3
+ 604	5
+ 39	8
+ 838	10
+ 547	5
+ 820	5
+ 361	2
+ 955	1
+ 0	0
+ 52	8
+ 826	5
+ 855	9
+ 938	5
+ 825	9
+ 43	9
+ 484	2
+ 173	1
+ 762	2
+ 935	6
+ 196	5
+ 107	0
+ 957	5
+ 254	9
+ 554	3
+ 926	6
+ 69	8
+ 58	9
+ 614	10
+ 393	4
+ 882	4
+ 317	4
+ 669	5
+ 454	4
+ 701	4
+ 32	9
+ 871	1
+ 913	8
+ 607	2
+ 740	2
+ 421	7
+ 767	5
+ 418	8
+ 414	0
+ 821	8
+ 470	7
+ 244	8
+ 69	9
+ 277	5
+ 345	10
+ 912	4
+ 875	8
+ 516	8
+ 611	1
+ 956	4
+ 285	4
+ 16	1
+ 867	4
+ 878	3
+ 466	7
+ 88	9
+ 401	3
+ 723	5
+ 245	0
+ 992	6
+ 978	9
+ 967	9
+ 687	5
+ 642	3
+ 607	6
+ 648	9
+ 974	7
+ 944	8
+ 98	8
+ 122	6
+ 520	2
+ 500	9
+ 541	2
+ 391	8
+ 223	4
+ 376	2
+ 288	3
+ 55	10
+ 827	7
+ 273	4
+ 294	9
+ 325	3
+ 585	3
+ 108	7
+ 92	2
+ 248	6
+ 440	7
+ 533	10
+ 971	9
+ 767	2
+ 308	1
+ 395	6
+ 487	4
+ 571	3
+ 146	8
+ 747	4
+ 765	1
+ 707	4
+ 342	8
+ 34	4
+ 46	3
+ 46	5
+ 30	6
+ 466	0
+ 504	2
+ 194	8
+ 378	6
+ 408	9
+ 38	10
+ 178	2
+ 823	9
+ 624	6
+ 997	3
+ 939	3
+ 147	10
+ 772	2
+ 255	8
+ 677	3
+ 397	1
+ 286	9
+ 378	5
+ 712	8
+ 69	1
+ 620	1
+ 98	8
+ 291	9
+ 722	9
+ 509	7
+ 245	4
+ 58	4
+ 421	8
+ 584	7
+ 648	3
+ 962	0
+ 405	2
+ 945	8
+ 727	7
+ 538	8
+ 776	2
+ 903	9
+ 956	2
+ 796	7
+ 108	3
+ 397	4
+ 753	5
+ 745	2
+ 285	3
+ 850	9
+ 591	8
+ 977	10
+ 59	9
+ 780	8
+ 578	3
+ 583	4
+ 476	5
+ 228	4
+ 679	0
+ 110	8
+ 329	5
+ 141	1
+ 963	9
+ 255	2
+ 215	1
+ 181	8
+ 917	2
+ 803	10
+ 80	6
+ 763	7
+ 900	3
+ 12	4
+ 831	2
+ 809	5
+ 264	9
+ 297	6
+ 427	4
+ 674	4
+ 324	9
+ 638	5
+ 34	8
+ 346	10
+ 978	1
+ 928	1
+ 730	7
+ 716	6
+ 36	7
+ 7	9
+ 969	8
+ 378	2
+ 735	7
+ 826	2
+ 113	5
+ 552	4
+ 429	2
+ 976	5
+ 10	3
+ 415	10
+ 470	3
+ 46	2
+ 33	8
+ 831	1
+ 490	8
+ 937	5
+ 654	3
+ 691	4
+ 990	5
+ 550	1
+ 17	1
+ 539	4
+ 292	5
+ 909	3
+ 837	3
+ 289	3
+ 666	3
+ 507	7
+ 96	3
+ 769	6
+ 176	7
+ 45	8
+ 21	7
+ 218	0
+ 253	8
+ 113	3
+ 870	7
+ 715	2
+ 167	6
+ 463	0
+ 947	8
+ 312	6
+ 87	8
+ 312	2
+ 157	1
+ 770	3
+ 787	8
+ 163	8
+ 551	4
+ 818	8
+ 150	9
+ 74	0
+ 583	8
+ 182	8
+ 414	6
+ 755	4
+ 397	1
+ 974	5
+ 886	3
+ 668	0
+ 368	4
+ 377	2
+ 253	5
+ 964	8
+ 921	8
+ 609	1
+ 713	7
+ 90	3
+ 472	3
+ 47	9
+ 917	8
+ 247	3
+ 869	2
+ 798	8
+ 508	5
+ 798	9
+ 905	2
+ 32	2
+ 714	10
+ 962	6
+ 777	6
+ 705	5
+ 253	8
+ 787	7
+ 67	8
+ 612	10
+ 636	9
+ 298	5
+ 80	1
+ 259	6
+ 563	1
+ 464	5
+ 232	5
+ 625	9
+ 491	6
+ 581	3
+ 157	3
+ 759	4
+ 82	5
+ 136	1
+ 380	7
+ 132	0
+ 607	4
+ 520	7
+ 526	8
+ 275	1
+ 837	7
+ 556	1
+ 235	2
+ 15	7
+ 768	6
+ 994	9
+ 882	8
+ 336	10
+ 299	5
+ 112	7
+ 220	2
+ 695	8
+ 675	2
+ 513	2
+ 995	8
+ 290	8
+ 527	8
+ 900	8
+ 27	9
+ 488	8
+ 510	5
+ 720	4
+ 235	1
+ 355	5
+ 528	5
+ 213	7
+ 711	9
+ 574	4
+ 122	1
+ 587	1
+ 876	9
+ 948	4
+ 723	8
+ 165	7
+ 764	7
+ 545	3
+ 134	3
+ 666	4
+ 321	0
+ 903	8
+ 489	1
+ 597	2
+ 23	2
+ 586	1
+ 259	2
+ 263	1
+ 50	2
+ 537	8
+ 60	7
+ 522	8
+ 354	1
+ 98	5
+ 331	8
+ 857	7
+ 786	8
+ 501	3
+ 876	1
+ 475	9
+ 269	1
+ 45	5
+ 234	3
+ 662	3
+ 518	2
+ 56	6
+ 900	6
+ 402	3
+ 644	5
+ 743	10
+ 264	6
+ 627	1
+ 360	1
+ 325	2
+ 226	8
+ 134	5
+ 861	2
+ 22	1
+ 486	7
+ 379	0
+ 882	4
+ 582	8
+ 12	10
+ 37	7
+ 484	8
+ 631	7
+ 379	3
+ 799	7
+ 387	1
+ 974	6
+ 925	1
+ 108	8
+ 287	1
+ 881	8
+ 813	3
+ 778	7
+ 695	4
+ 478	7
+ 344	5
+ 364	8
+ 294	10
+ 577	7
+ 254	4
+ 412	6
+ 500	4
+ 254	4
+ 495	4
+ 211	8
+ 491	1
+ 555	3
+ 352	3
+ 1000	0
+ 693	5
+ 755	0
+ 992	1
+ 865	3
+ 114	4
+ 959	4
+ 818	4
+ 9	3
+ 757	3
+ 743	3
+ 625	10
+ 34	1
+ 46	6
+ 421	4
+ 923	4
+ 445	6
+ 898	2
+ 653	9
+ 319	5
+ 175	4
+ 960	1
+ 802	8
+ 505	8
+ 96	3
+ 75	8
+ 515	7
+ 793	5
+ 817	8
+ 139	2
+ 236	1
+ 658	7
+ 677	6
+ 882	3
+ 445	2
+ 848	6
+ 635	8
+ 754	4
+ 586	3
+ 249	7
+ 523	3
+ 522	0
+ 24	3
+ 587	8
+ 153	7
+ 78	4
+ 787	7
+ 71	5
+ 291	10
+ 794	7
+ 155	6
+ 356	8
+ 451	1
+ 228	0
+ 370	5
+ 719	9
+ 801	2
+ 930	8
+ 556	5
+ 667	7
+ 242	7
+ 98	0
+ 481	2
+ 493	8
+ 123	3
+ 508	3
+ 929	9
+ 68	4
+ 974	3
+ 417	3
+ 772	1
+ 237	6
+ 378	2
+ 399	9
+ 683	1
+ 642	9
+ 811	7
+ 954	3
+ 910	4
+ 64	0
+ 734	6
+ 310	7
+ 437	4
+ 43	4
+ 674	5
+ 756	4
+ 596	10
+ 20	10
+ 158	4
+ 907	8
+ 485	5
+ 766	3
+ 290	7
+ 588	2
+ 167	7
+ 233	9
+ 224	5
+ 564	7
+ 922	6
+ 73	6
+ 67	8
+ 41	7
+ 820	1
+ 637	10
+ 480	5
+ 820	10
+ 94	6
+ 260	4
+ 306	8
+ 584	5
+ 500	8
+ 374	7
+ 361	9
+ 385	3
+ 545	5
+ 877	6
+ 286	9
+ 275	1
+ 979	9
+ 85	5
+ 457	9
+ 424	6
+ 492	7
+ 936	8
+ 531	5
+ 271	0
+ 337	6
+ 755	7
+ 583	1
+ 980	1
+ 599	9
+ 739	9
+ 776	0
+ 992	8
+ 926	1
+ 215	4
+ 982	6
+ 935	5
+ 322	9
+ 272	9
+ 391	5
+ 885	7
+ 189	6
+ 426	8
+ 780	4
+ 899	4
+ 264	6
+ 264	0
+ 652	3
+ 796	6
+ 332	0
+ 961	3
+ 649	9
+ 789	10
+ 767	1
+ 825	2
+ 605	7
+ 886	8
+ 349	3
+ 566	1
+ 719	5
+ 508	10
+ 103	8
+ 23	8
+ 28	8
+ 333	4
+ 830	3
+ 675	5
+ 190	5
+ 450	10
+ 525	3
+ 115	1
+ 984	0
+ 924	3
+ 313	5
+ 463	0
+ 955	10
+ 15	1
+ 743	0
+ 813	8
+ 858	1
+ 131	7
+ 440	8
+ 167	6
+ 270	6
+ 587	8
+ 892	7
+ 925	9
+ 702	8
+ 210	0
+ 339	7
+ 47	3
+ 643	1
+ 351	4
+ 101	2
+ 157	10
+ 310	3
+ 647	7
+ 93	8
+ 380	4
+ 432	10
+ 158	3
+ 668	1
+ 201	4
+ 933	4
+ 386	3
+ 83	4
+ 566	7
+ 496	9
+ 113	6
+ 81	3
+ 556	4
+ 557	2
+ 140	7
+ 16	5
+ 13	4
+ 487	2
+ 772	2
+ 253	10
+ 526	2
+ 384	9
+ 458	5
+ 345	0
+ 194	8
+ 941	3
+ 438	0
+ 577	10
+ 413	1
+ 196	6
+ 784	2
+ 74	8
+ 660	6
+ 967	4
+ 716	2
+ 405	2
+ 407	8
+ 154	9
+ 256	5
+ 888	4
+ 341	8
+ 757	8
+ 852	3
+ 771	3
+ 468	10
+ 819	3
+ 179	9
+ 49	8
+ 454	0
+ 271	2
+ 238	7
+ 413	6
+ 465	6
+ 509	7
+ 67	4
+ 171	4
+ 226	9
+ 186	1
+ 261	10
+ 343	7
+ 924	2
+ 982	1
+ 55	0
+ 942	5
+ 48	2
+ 679	3
+ 890	1
+ 930	4
+ 659	4
+ 75	7
+ 836	2
+ 133	1
+ 173	3
+ 141	4
+ 277	5
+ 164	2
+ 646	1
+ 305	7
+ 178	2
+ 210	2
+ 460	9
+ 512	4
+ 981	4
+ 705	6
+ 881	8
+ 366	7
+ 26	5
+ 780	2
+ 818	9
+ 634	1
+ 404	8
+ 296	0
+ 945	6
+ 751	1
+ 848	10
+ 349	3
+ 850	9
+ 658	8
+ 303	4
+ 471	2
+ 143	8
+ 902	2
+ 335	7
+ 368	2
+ 602	0
+ 248	0
+ 800	5
+ 55	7
+ 145	8
+ 868	10
+ 767	2
+ 301	6
+ 78	10
+ 447	4
+ 322	9
+ 566	5
+ 754	5
+ 633	1
+ 149	0
+ 242	8
+ 2	5
+ 757	8
+ 35	8
+ 547	2
+ 618	4
+ 174	4
+ 631	5
+ 1	7
+ 434	4
+ 91	8
+ 366	7
+ 221	1
+ 124	9
+ 208	3
+ 855	5
+ 25	9
+ 941	8
+ 660	10
+ 593	2
+ 157	2
+ 621	3
+ 596	3
+ 806	6
+ 962	2
+ 45	1
+ 996	4
+ 709	2
+ 530	8
+ 72	7
+ 107	9
+ 189	1
+ 784	1
+ 913	4
+ 106	5
+ 650	3
+ 717	3
+ 594	3
+ 524	4
+ 910	5
+ 640	10
+ 538	6
+ 365	2
+ 854	9
+ 80	9
+ 634	2
+ 852	8
+ 318	6
+ 953	2
+ 80	1
+ 737	7
+ 323	5
+ 2	9
+ 766	5
+ 317	7
+ 11	10
+ 630	5
+ 593	10
+ 795	4
+ 891	9
+ 372	5
+ 61	2
+ 348	4
+ 861	3
+ 610	9
+ 360	3
+ 672	7
+ 800	7
+ 599	6
+ 199	9
+ 242	2
+ 873	9
+ 759	5
+ 868	6
+ 912	8
+ 429	3
+ 284	5
+ 507	6
+ 869	4
+ 933	5
+ 309	3
+ 825	10
+ 976	6
+ 654	6
+ 190	9
+ 491	4
+ 63	4
+ 304	8
+ 829	2
+ 377	7
+ 931	8
+ 24	2
+ 295	5
+ 848	2
+ 899	8
+ 642	2
+ 74	5
+ 188	0
+ 92	8
+ 624	3
+ 695	1
+ 714	8
+ 479	0
+ 581	3
+ 191	10
+ 49	1
+ 763	1
+ 337	1
+ 604	2
+ 222	5
+ 965	9
+ 712	0
+ 332	9
+ 88	4
+ 742	7
+ 706	4
+ 828	4
+ 196	3
+ 438	8
+ 616	6
+ 735	7
+ 751	5
+ 738	1
+ 556	3
+ 272	8
+ 846	2
+ 643	6
+ 277	10
+ 457	4
+ 398	2
+ 77	1
+ 636	9
+ 524	8
+ 213	10
+ 609	8
+ 591	3
+ 493	3
+ 842	2
+ 430	4
+ 573	7
+ 177	4
+ 940	8
+ 977	2
+ 795	4
+ 581	2
+ 633	7
+ 297	3
+ 564	8
+ 101	8
+ 783	7
+ 605	4
+ 55	1
+ 716	9
+ 329	1
+ 296	9
+ 847	5
+ 321	8
+ 294	3
+ 3	1
+ 731	6
+ 281	4
+ 243	6
+ 634	8
+ 399	7
+ 583	2
+ 445	2
+ 555	5
+ 286	3
+ 398	6
+ 417	7
+ 517	3
+ 167	8
+ 51	5
+ 135	1
+ 549	9
+ 638	8
+ 231	9
+ 409	9
+ 687	8
+ 599	3
+ 989	0
+ 458	5
+ 545	7
+ 816	9
+ 359	2
+ 637	9
+ 496	8
+ 713	5
+ 265	8
+ 601	8
+ 715	2
+ 645	9
+ 119	1
+ 810	8
+ 862	4
+ 76	9
+ 454	5
+ 395	10
+ 279	2
+ 942	6
+ 442	6
+ 513	9
+ 383	2
+ 486	6
+ 73	1
+ 463	8
+ 325	1
+ 733	4
+ 162	5
+ 251	0
+ 952	3
+ 874	4
+ 862	3
+ 405	1
+ 479	3
+ 778	9
+ 925	3
+ 860	3
+ 516	3
+ 956	6
+ 433	4
+ 377	8
+ 527	1
+ 203	7
+ 654	5
+ 713	6
+ 781	6
+ 12	6
+ 856	4
+ 783	3
+ 763	6
+ 257	7
+ 852	1
+ 995	4
+ 463	10
+ 957	9
+ 369	3
+ 654	9
+ 445	9
+ 584	1
+ 310	3
+ 704	1
+ 884	7
+ 734	7
+ 132	5
+ 75	9
+ 79	3
+ 582	9
+ 449	6
+ 299	9
+ 527	3
+ 808	9
+ 590	5
+ 791	0
+ 318	4
+ 134	6
+ 671	8
+ 721	6
+ 554	5
+ 295	7
+ 973	4
+ 582	1
+ 702	2
+ 983	2
+ 741	3
+ 63	3
+ 538	9
+ 163	1
+ 333	10
+ 164	7
+ 329	3
+ 280	10
+ 136	0
+ 555	7
+ 455	8
+ 377	4
+ 220	10
+ 480	9
+ 122	5
+ 72	9
+ 744	1
+ 130	3
+ 6	3
+ 410	3
+ 248	6
+ 989	6
+ 872	3
+ 577	0
+ 270	1
+ 697	7
+ 981	1
+ 153	2
+ 32	6
+ 122	2
+ 96	2
+ 16	8
+ 329	1
+ 122	3
+ 440	5
+ 673	7
+ 107	7
+ 265	10
+ 932	8
+ 986	2
+ 972	7
+ 927	10
+ 757	1
+ 154	8
+ 713	3
+ 942	8
+ 470	10
+ 649	8
+ 104	8
+ 134	5
+ 305	8
+ 232	4
+ 469	5
+ 390	4
+ 338	4
+ 602	3
+ 58	5
+ 264	8
+ 609	4
+ 603	3
+ 694	5
+ 131	2
+ 503	8
+ 962	6
+ 552	1
+ 152	9
+ 902	4
+ 268	4
+ 881	7
+ 772	2
+ 33	4
+ 529	1
+ 903	8
+ 905	5
+ 210	5
+ 833	9
+ 53	10
+ 67	6
+ 744	0
+ 164	3
+ 125	3
+ 153	0
+ 699	4
+ 398	6
+ 78	2
+ 798	1
+ 544	3
+ 202	4
+ 119	1
+ 959	3
+ 615	8
+ 232	7
+ 756	3
+ 224	5
+ 328	4
+ 797	5
+ 703	10
+ 480	4
+ 371	9
+ 982	4
+ 49	8
+ 561	6
+ 106	8
+ 40	2
+ 869	10
+ 554	5
+ 790	8
+ 151	5
+ 85	4
+ 47	4
+ 763	8
+ 866	5
+ 794	3
+ 868	2
+ 225	8
+ 615	3
+ 629	2
+ 866	7
+ 937	9
+ 960	8
+ 904	5
+ 290	7
+ 301	4
+ 241	4
+ 816	3
+ 799	6
+ 131	7
+ 45	9
+ 12	9
+ 90	2
+ 762	7
+ 510	4
+ 880	4
+ 126	8
+ 282	1
+ 623	2
+ 601	9
+ 880	9
+ 354	1
+ 287	2
+ 408	1
+ 749	5
+ 753	8
+ 464	8
+ 707	6
+ 2	5
+ 258	5
+ 859	1
+ 888	10
+ 956	2
+ 71	6
+ 355	7
+ 492	2
+ 574	8
+ 355	9
+ 15	8
+ 948	8
+ 302	7
+ 558	8
+ 466	3
+ 320	5
+ 733	6
+ 980	6
+ 716	9
+ 577	7
+ 37	6
+ 251	4
+ 321	7
+ 627	9
+ 588	10
+ 756	6
+ 746	7
+ 367	0
+ 405	9
+ 814	9
+ 191	1
+ 338	9
+ 712	3
+ 517	4
+ 186	1
+ 100	2
+ 743	4
+ 615	1
+ 93	2
+ 958	7
+ 225	7
+ 284	10
+ 418	7
+ 19	8
+ 577	8
+ 693	8
+ 967	0
+ 692	7
+ 349	2
+ 106	5
+ 303	2
+ 758	0
+ 557	4
+ 109	7
+ 616	1
+ 332	8
+ 782	6
+ 812	2
+ 267	8
+ 22	8
+ 665	7
+ 612	6
+ 746	3
+ 309	1
+ 512	4
+ 630	8
+ 622	4
+ 860	2
+ 762	10
+ 830	4
+ 37	2
+ 219	8
+ 777	0
+ 19	0
+ 863	0
+ 888	5
+ 756	5
+ 159	5
+ 804	5
+ 597	3
+ 884	2
+ 131	5
+ 616	10
+ 685	4
+ 961	5
+ 756	10
+ 675	10
+ 818	5
+ 6	8
+ 496	9
+ 878	4
+ 397	6
+ 884	6
+ 135	7
+ 23	7
+ 3	9
+ 959	1
+ 412	6
+ 125	1
+ 953	1
+ 611	7
+ 84	3
+ 683	9
+ 739	7
+ 738	2
+ 559	6
+ 619	10
+ 249	5
+ 511	4
+ 190	5
+ 116	2
+ 442	1
+ 327	9
+ 649	5
+ 951	6
+ 538	6
+ 310	6
+ 848	10
+ 524	6
+ 684	3
+ 822	2
+ 878	4
+ 198	1
+ 943	7
+ 512	1
+ 244	6
+ 325	7
+ 702	7
+ 539	4
+ 104	5
+ 952	6
+ 52	3
+ 264	9
+ 257	8
+ 487	9
+ 50	3
+ 183	9
+ 748	4
+ 56	7
+ 91	6
+ 823	3
+ 195	1
+ 21	9
+ 801	6
+ 247	9
+ 50	2
+ 546	1
+ 462	8
+ 2	7
+ 597	5
+ 659	6
+ 797	8
+ 575	5
+ 224	6
+ 236	3
+ 198	1
+ 650	4
+ 208	7
+ 289	0
+ 231	5
+ 913	3
+ 735	5
+ 383	2
+ 268	4
+ 915	9
+ 874	6
+ 512	7
+ 417	1
+ 215	6
+ 718	5
+ 955	9
+ 511	6
+ 309	7
+ 275	6
+ 727	5
+ 133	6
+ 786	9
+ 99	2
+ 64	4
+ 554	10
+ 233	4
+ 554	7
+ 98	10
+ 832	3
+ 611	5
+ 765	6
+ 466	3
+ 170	8
+ 995	4
+ 371	7
+ 951	5
+ 363	7
+ 371	5
+ 907	4
+ 830	5
+ 414	1
+ 889	10
+ 808	10
+ 937	6
+ 301	5
+ 189	1
+ 114	7
+ 343	3
+ 429	3
+ 729	8
+ 61	7
+ 304	4
+ 416	7
+ 886	3
+ 110	7
+ 784	5
+ 779	7
+ 491	6
+ 660	4
+ 226	10
+ 976	4
+ 28	1
+ 71	4
+ 374	5
+ 709	1
+ 300	8
+ 782	6
+ 193	2
+ 280	1
+ 521	4
+ 794	3
+ 913	6
+ 978	4
+ 159	6
+ 833	4
+ 600	8
+ 801	6
+ 899	9
+ 999	3
+ 371	7
+ 376	7
+ 477	2
+ 276	7
+ 356	6
+ 749	9
+ 945	5
+ 183	9
+ 116	2
+ 262	3
+ 799	1
+ 661	4
+ 904	5
+ 28	8
+ 334	0
+ 76	7
+ 735	5
+ 376	2
+ 609	7
+ 882	10
+ 207	6
+ 843	2
+ 174	0
+ 10	3
+ 187	3
+ 565	10
+ 366	2
+ 386	3
+ 689	4
+ 73	0
+ 441	1
+ 727	2
+ 600	1
+ 388	2
+ 756	3
+ 176	10
+ 901	0
+ 115	1
+ 45	1
+ 364	2
+ 396	9
+ 218	8
+ 156	6
+ 32	8
+ 18	1
+ 867	5
+ 254	6
+ 635	9
+ 699	0
+ 65	5
+ 293	2
+ 417	2
+ 259	5
+ 268	3
+ 656	6
+ 535	1
+ 562	8
+ 814	7
+ 357	8
+ 563	4
+ 952	4
+ 834	2
+ 25	5
+ 60	7
+ 492	1
+ 178	8
+ 365	6
+ 977	6
+ 127	2
+ 928	8
+ 877	5
+ 834	4
+ 216	6
+ 157	6
+ 495	7
+ 949	4
+ 150	8
+ 653	2
+ 252	7
+ 898	7
+ 838	1
+ 527	2
+ 671	5
+ 827	8
+ 750	8
+ 581	6
+ 217	4
+ 66	4
+ 64	2
+ 7	6
+ 943	10
+ 6	1
+ 738	7
+ 267	10
+ 372	2
+ 733	2
+ 242	3
+ 413	9
+ 765	2
+ 712	5
+ 994	3
+ 142	2
+ 708	2
+ 645	8
+ 431	7
+ 331	4
+ 608	3
+ 466	3
+ 996	7
+ 336	4
+ 899	1
+ 577	1
+ 330	10
+ 54	1
+ 229	8
+ 609	2
+ 59	8
+ 435	8
+ 959	1
+ 539	4
+ 733	9
+ 763	3
+ 207	2
+ 687	2
+ 961	0
+ 570	9
+ 93	1
+ 1	4
+ 137	1
+ 517	4
+ 821	1
+ 590	9
+ 878	0
+ 646	8
+ 106	2
+ 226	8
+ 56	10
+ 180	3
+ 218	9
+ 466	2
+ 891	0
+ 39	10
+ 183	0
+ 407	3
+ 95	9
+ 686	9
+ 51	3
+ 795	9
+ 301	4
+ 765	4
+ 627	10
+ 246	7
+ 981	4
+ 946	2
+ 294	4
+ 378	2
+ 448	4
+ 170	6
+ 457	6
+ 950	6
+ 501	6
+ 467	6
+ 911	3
+ 480	2
+ 704	2
+ 619	3
+ 237	9
+ 14	2
+ 291	10
+ 416	6
+ 372	8
+ 770	8
+ 212	9
+ 451	7
+ 516	4
+ 221	0
+ 37	7
+ 568	9
+ 950	0
+ 160	7
+ 293	8
+ 985	5
+ 644	10
+ 747	9
+ 960	2
+ 519	3
+ 958	3
+ 151	2
+ 227	6
+ 838	7
+ 3	1
+ 760	0
+ 747	3
+ 988	7
+ 376	1
+ 351	7
+ 928	3
+ 198	6
+ 336	9
+ 506	3
+ 109	0
+ 627	1
+ 312	8
+ 236	5
+ 380	1
+ 283	4
+ 133	0
+ 423	9
+ 371	4
+ 577	7
+ 559	9
+ 415	5
+ 264	6
+ 58	6
+ 559	6
+ 896	7
+ 588	5
+ 734	9
+ 302	10
+ 440	7
+ 45	7
+ 66	2
+ 766	5
+ 58	1
+ 899	6
+ 883	5
+ 562	3
+ 945	8
+ 911	0
+ 427	5
+ 566	3
+ 138	2
+ 847	9
+ 55	1
+ 842	5
+ 832	9
+ 218	9
+ 66	10
+ 386	1
+ 120	3
+ 758	0
+ 743	3
+ 300	7
+ 147	2
+ 690	6
+ 681	3
+ 898	8
+ 411	7
+ 691	5
+ 895	5
+ 960	7
+ 420	2
+ 625	5
+ 162	0
+ 610	3
+ 296	4
+ 283	0
+ 688	6
+ 726	8
+ 794	4
+ 410	5
+ 673	3
+ 294	1
+ 54	10
+ 549	9
+ 518	5
+ 677	9
+ 687	3
+ 425	8
+ 314	0
+ 130	6
+ 402	4
+ 648	1
+ 997	4
+ 926	8
+ 791	3
+ 267	5
+ 645	6
+ 547	7
+ 546	1
+ 649	1
+ 605	3
+ 3	3
+ 628	4
+ 141	9
+ 462	3
+ 551	9
+ 684	2
+ 954	7
+ 574	9
+ 472	4
+ 217	7
+ 828	9
+ 299	4
+ 562	8
+ 471	2
+ 909	1
+ 536	9
+ 367	2
+ 339	5
+ 106	8
+ 779	7
+ 664	5
+ 856	6
+ 144	4
+ 499	6
+ 796	7
+ 353	6
+ 579	7
+ 999	1
+ 497	5
+ 351	4
+ 546	9
+ 317	9
+ 51	7
+ 421	2
+ 456	2
+ 813	1
+ 664	7
+ 738	8
+ 100	2
+ 422	9
+ 953	8
+ 520	5
+ 428	5
+ 672	9
+ 990	0
+ 331	5
+ 910	6
+ 448	10
+ 305	9
+ 118	8
+ 70	9
+ 881	7
+ 601	6
+ 541	7
+ 855	10
+ 597	8
+ 739	1
+ 341	2
+ 637	0
+ 93	6
+ 37	4
+ 162	9
+ 73	6
+ 908	4
+ 480	0
+ 139	6
+ 957	0
+ 284	6
+ 638	8
+ 259	5
+ 788	9
+ 302	5
+ 974	6
+ 695	6
+ 656	8
+ 237	7
+ 212	4
+ 639	3
+ 9	5
+ 663	5
+ 573	8
+ 39	5
+ 821	3
+ 88	5
+ 148	3
+ 952	9
+ 204	3
+ 464	2
+ 896	2
+ 789	6
+ 947	0
+ 244	2
+ 425	9
+ 444	4
+ 430	1
+ 924	0
+ 909	10
+ 533	7
+ 286	6
+ 189	4
+ 969	1
+ 370	2
+ 394	8
+ 350	3
+ 993	1
+ 842	9
+ 165	1
+ 99	6
+ 969	5
+ 24	4
+ 651	9
+ 401	6
+ 911	9
+ 290	2
+ 556	5
+ 631	5
+ 619	0
+ 696	0
+ 835	0
+ 303	8
+ 185	1
+ 767	3
+ 231	9
+ 940	2
+ 410	10
+ 598	1
+ 912	10
+ 621	8
+ 934	9
+ 20	5
+ 389	7
+ 14	0
+ 651	7
+ 22	5
+ 757	3
+ 313	9
+ 471	1
+ 292	7
+ 947	2
+ 902	4
+ 196	5
+ 418	1
+ 500	0
+ 931	4
+ 949	10
+ 924	3
+ 601	9
+ 348	3
+ 648	4
+ 738	4
+ 695	1
+ 347	2
+ 132	6
+ 867	1
+ 872	8
+ 436	1
+ 269	9
+ 176	8
+ 893	1
+ 203	8
+ 59	1
+ 181	7
+ 65	5
+ 912	7
+ 898	7
+ 118	6
+ 702	5
+ 758	8
+ 105	6
+ 913	10
+ 395	3
+ 45	7
+ 204	2
+ 433	1
+ 329	6
+ 939	4
+ 764	1
+ 48	8
+ 650	10
+ 542	5
+ 610	7
+ 141	3
+ 126	9
+ 146	2
+ 525	1
+ 208	9
+ 409	3
+ 584	6
+ 474	0
+ 710	8
+ 654	6
+ 190	4
+ 770	2
+ 247	4
+ 198	8
+ 968	8
+ 448	1
+ 121	6
+ 8	3
+ 805	5
+ 326	0
+ 452	7
+ 265	0
+ 347	7
+ 53	1
+ 542	7
+ 706	7
+ 124	5
+ 970	4
+ 896	2
+ 159	9
+ 977	6
+ 972	1
+ 182	10
+ 364	10
+ 513	7
+ 999	10
+ 425	3
+ 1000	8
+ 3	1
+ 829	5
+ 759	5
+ 277	9
+ 12	2
+ 254	9
+ 415	4
+ 772	4
+ 21	7
+ 490	2
+ 725	9
+ 189	2
+ 544	2
+ 202	10
+ 452	2
+ 741	5
+ 254	6
+ 1000	0
+ 106	3
+ 896	1
+ 523	1
+ 27	9
+ 563	8
+ 330	6
+ 544	8
+ 786	3
+ 674	10
+ 506	2
+ 162	7
+ 186	6
+ 910	9
+ 69	2
+ 496	1
+ 177	6
+ 346	1
+ 720	9
+ 223	7
+ 807	8
+ 546	1
+ 369	1
+ 958	2
+ 358	6
+ 129	9
+ 849	3
+ 573	0
+ 906	5
+ 961	10
+ 646	5
+ 45	8
+ 59	4
+ 896	8
+ 259	1
+ 526	1
+ 904	1
+ 204	3
+ 162	2
+ 428	5
+ 793	6
+ 385	6
+ 849	10
+ 676	8
+ 440	6
+ 731	1
+ 94	8
+ 909	2
+ 166	8
+ 933	4
+ 923	5
+ 492	8
+ 531	7
+ 100	7
+ 858	5
+ 214	7
+ 86	6
+ 292	9
+ 556	10
+ 691	10
+ 604	4
+ 82	7
+ 197	10
+ 851	4
+ 796	8
+ 788	7
+ 243	3
+ 547	8
+ 975	6
+ 467	8
+ 176	7
+ 484	3
+ 279	8
+ 198	8
+ 743	9
+ 832	3
+ 310	9
+ 46	5
+ 906	9
+ 871	7
+ 681	7
+ 422	9
+ 938	10
+ 698	9
+ 615	2
+ 747	8
+ 846	2
+ 53	1
+ 6	3
+ 961	7
+ 139	8
+ 97	4
+ 707	1
+ 957	6
+ 40	8
+ 314	7
+ 487	7
+ 645	4
+ 704	3
+ 339	3
+ 508	1
+ 110	4
+ 315	2
+ 479	3
+ 414	4
+ 70	6
+ 231	2
+ 3	9
+ 311	10
+ 550	4
+ 788	9
+ 72	3
+ 600	7
+ 700	3
+ 60	0
+ 623	6
+ 124	7
+ 922	4
+ 897	4
+ 760	3
+ 839	8
+ 864	1
+ 998	9
+ 9	3
+ 827	6
+ 660	6
+ 423	7
+ 891	0
+ 450	6
+ 327	5
+ 630	10
+ 78	8
+ 685	0
+ 194	6
+ 401	10
+ 893	2
+ 785	8
+ 311	8
+ 625	3
+ 92	5
+ 878	8
+ 68	3
+ 484	10
+ 325	9
+ 550	7
+ 444	2
+ 603	5
+ 935	3
+ 522	1
+ 870	9
+ 82	8
+ 163	9
+ 521	5
+ 650	1
+ 794	7
+ 598	7
+ 494	7
+ 974	10
+ 625	3
+ 911	2
+ 951	4
+ 356	6
+ 877	3
+ 842	4
+ 419	7
+ 322	5
+ 476	5
+ 369	10
+ 960	0
+ 143	8
+ 761	7
+ 426	3
+ 408	4
+ 233	0
+ 698	1
+ 209	6
+ 499	6
+ 203	4
+ 856	0
+ 775	3
+ 757	1
+ 776	2
+ 583	1
+ 229	5
+ 164	4
+ 297	9
+ 114	7
+ 180	5
+ 122	4
+ 555	8
+ 556	8
+ 469	1
+ 328	7
+ 431	2
+ 717	2
+ 459	5
+ 302	2
+ 706	9
+ 380	9
+ 428	5
+ 308	7
+ 468	4
+ 447	6
+ 944	6
+ 60	5
+ 390	6
+ 262	9
+ 672	6
+ 531	1
+ 774	2
+ 307	2
+ 721	6
+ 468	4
+ 495	8
+ 363	9
+ 392	7
+ 648	9
+ 93	1
+ 508	0
+ 664	6
+ 536	1
+ 185	8
+ 913	9
+ 390	4
+ 959	2
+ 692	3
+ 397	4
+ 877	9
+ 841	4
+ 713	2
+ 295	1
+ 875	9
+ 965	10
+ 37	5
+ 6	7
+ 42	5
+ 755	2
+ 342	7
+ 84	7
+ 112	0
+ 895	8
+ 310	3
+ 218	2
+ 158	1
+ 559	9
+ 264	9
+ 976	1
+ 796	9
+ 108	8
+ 413	1
+ 533	5
+ 658	3
+ 682	10
+ 956	8
+ 731	1
+ 809	6
+ 873	1
+ 918	1
+ 307	1
+ 152	9
+ 947	4
+ 719	9
+ 555	5
+ 863	7
+ 347	3
+ 778	9
+ 731	4
+ 168	4
+ 435	1
+ 179	2
+ 193	10
+ 791	1
+ 108	7
+ 159	4
+ 786	3
+ 280	7
+ 726	10
+ 655	3
+ 512	5
+ 944	9
+ 793	7
+ 739	5
+ 158	9
+ 937	6
+ 32	1
+ 758	2
+ 104	5
+ 292	2
+ 259	5
+ 626	0
+ 761	9
+ 777	5
+ 903	4
+ 767	4
+ 949	7
+ 274	7
+ 434	0
+ 266	6
+ 921	2
+ 184	10
+ 318	9
+ 178	4
+ 491	5
+ 633	8
+ 921	3
+ 795	7
+ 164	6
+ 168	1
+ 3	9
+ 483	10
+ 647	8
+ 694	1
+ 771	10
+ 673	7
+ 163	9
+ 644	5
+ 799	8
+ 903	3
+ 292	5
+ 40	2
+ 794	8
+ 895	10
+ 407	1
+ 25	4
+ 999	5
+ 362	6
+ 265	1
+ 727	0
+ 16	4
+ 727	2
+ 257	4
+ 660	1
+ 193	6
+ 345	5
+ 98	4
+ 698	9
+ 221	6
+ 850	6
+ 656	9
+ 37	7
+ 383	4
+ 301	6
+ 455	0
+ 684	5
+ 428	4
+ 650	7
+ 781	3
+ 740	10
+ 872	1
+ 459	10
+ 471	2
+ 863	7
+ 749	7
+ 319	4
+ 589	4
+ 59	10
+ 755	4
+ 621	2
+ 388	3
+ 681	8
+ 716	3
+ 501	5
+ 641	2
+ 471	5
+ 327	9
+ 484	8
+ 87	3
+ 490	8
+ 60	8
+ 241	6
+ 166	3
+ 622	9
+ 661	2
+ 132	0
+ 547	8
+ 865	3
+ 144	4
+ 760	8
+ 606	2
+ 299	9
+ 162	8
+ 731	2
+ 130	2
+ 85	2
+ 30	3
+ 840	2
+ 627	5
+ 117	3
+ 705	2
+ 337	3
+ 61	2
+ 515	2
+ 566	3
+ 991	2
+ 506	3
+ 105	7
+ 74	8
+ 916	2
+ 57	0
+ 395	1
+ 328	2
+ 282	10
+ 697	4
+ 243	4
+ 647	6
+ 654	7
+ 781	2
+ 914	3
+ 444	9
+ 520	9
+ 196	6
+ 618	3
+ 461	5
+ 474	5
+ 535	9
+ 604	9
+ 105	9
+ 818	8
+ 285	1
+ 205	9
+ 641	9
+ 641	4
+ 28	6
+ 768	5
+ 461	3
+ 421	7
+ 913	0
+ 927	4
+ 573	4
+ 892	1
+ 271	5
+ 971	4
+ 382	8
+ 179	7
+ 851	4
+ 600	5
+ 243	2
+ 913	3
+ 796	7
+ 742	3
+ 969	2
+ 914	9
+ 202	8
+ 257	8
+ 243	1
+ 882	5
+ 644	9
+ 891	0
+ 643	1
+ 694	5
+ 454	3
+ 986	7
+ 535	9
+ 967	3
+ 580	7
+ 588	5
+ 871	5
+ 432	1
+ 344	7
+ 847	6
+ 837	7
+ 100	5
+ 583	10
+ 508	2
+ 61	2
+ 721	5
+ 497	7
+ 211	0
+ 606	2
+ 363	2
+ 887	10
+ 736	8
+ 454	2
+ 831	8
+ 858	7
+ 384	7
+ 408	5
+ 176	10
+ 475	7
+ 218	5
+ 887	9
+ 51	4
+ 646	3
+ 415	3
+ 440	8
+ 438	3
+ 729	2
+ 86	2
+ 344	9
+ 981	2
+ 596	4
+ 896	0
+ 850	1
+ 995	3
+ 756	2
+ 861	6
+ 152	9
+ 26	8
+ 174	4
+ 50	6
+ 218	5
+ 942	9
+ 663	0
+ 131	0
+ 944	1
+ 208	5
+ 477	1
+ 544	3
+ 176	5
+ 652	9
+ 752	5
+ 574	9
+ 424	6
+ 702	6
+ 41	8
+ 212	3
+ 241	2
+ 207	9
+ 181	3
+ 911	1
+ 450	1
+ 665	9
+ 222	2
+ 254	4
+ 748	9
+ 329	5
+ 418	9
+ 405	8
+ 504	1
+ 441	5
+ 860	7
+ 803	1
+ 807	0
+ 4	10
+ 348	9
+ 114	8
+ 33	8
+ 725	3
+ 988	10
+ 653	7
+ 885	10
+ 238	3
+ 886	6
+ 146	4
+ 751	6
+ 934	6
+ 240	7
+ 712	0
+ 748	7
+ 35	1
+ 631	1
+ 894	7
+ 928	6
+ 920	9
+ 598	6
+ 654	5
+ 556	9
+ 786	4
+ 535	9
+ 832	3
+ 518	8
+ 896	8
+ 504	6
+ 804	3
+ 324	8
+ 347	10
+ 989	2
+ 619	9
+ 860	5
+ 834	5
+ 113	5
+ 942	7
+ 380	7
+ 112	9
+ 659	9
+ 200	2
+ 711	1
+ 934	2
+ 704	7
+ 466	0
+ 578	8
+ 983	6
+ 55	6
+ 485	9
+ 142	3
+ 373	3
+ 808	3
+ 925	2
+ 43	0
+ 102	7
+ 981	3
+ 878	7
+ 398	8
+ 906	1
+ 551	4
+ 129	1
+ 186	1
+ 697	2
+ 715	2
+ 156	9
+ 502	5
+ 112	3
+ 844	0
+ 497	9
+ 74	6
+ 589	1
+ 900	5
+ 747	3
+ 280	7
+ 399	8
+ 26	5
+ 961	2
+ 641	7
+ 453	4
+ 840	6
+ 212	3
+ 138	3
+ 651	10
+ 362	1
+ 869	4
+ 746	5
+ 490	6
+ 925	2
+ 943	2
+ 890	3
+ 36	9
+ 870	10
+ 128	5
+ 655	6
+ 866	5
+ 190	1
+ 837	3
+ 403	5
+ 310	8
+ 636	2
+ 200	4
+ 637	7
+ 28	6
+ 927	10
+ 766	8
+ 313	8
+ 733	2
+ 798	9
+ 695	5
+ 443	6
+ 948	6
+ 640	8
+ 960	0
+ 274	3
+ 808	9
+ 449	0
+ 292	1
+ 698	3
+ 648	6
+ 291	4
+ 443	6
+ 215	2
+ 788	0
+ 37	5
+ 467	5
+ 44	4
+ 112	7
+ 200	1
+ 727	5
+ 342	5
+ 383	8
+ 542	7
+ 877	2
+ 995	5
+ 866	3
+ 938	3
+ 891	2
+ 484	7
+ 167	5
+ 162	6
+ 1	2
+ 48	1
+ 890	2
+ 186	6
+ 721	5
+ 151	1
+ 318	7
+ 779	2
+ 934	8
+ 719	8
+ 61	7
+ 108	10
+ 810	6
+ 632	10
+ 114	8
+ 610	1
+ 0	7
+ 229	9
+ 906	4
+ 506	6
+ 942	7
+ 731	3
+ 350	5
+ 455	3
+ 284	2
+ 83	3
+ 830	2
+ 297	6
+ 783	9
+ 617	9
+ 723	2
+ 12	7
+ 885	2
+ 614	8
+ 656	1
+ 418	6
+ 777	1
+ 858	1
+ 659	3
+ 411	9
+ 486	5
+ 288	3
+ 685	6
+ 957	5
+ 514	6
+ 365	2
+ 801	4
+ 961	7
+ 618	6
+ 477	3
+ 695	9
+ 871	5
+ 44	7
+ 600	7
+ 42	0
+ 646	5
+ 504	9
+ 845	2
+ 520	8
+ 657	0
+ 375	0
+ 272	2
+ 398	2
+ 862	0
+ 809	3
+ 290	5
+ 234	2
+ 976	3
+ 891	6
+ 982	9
+ 587	6
+ 461	1
+ 563	3
+ 280	1
+ 107	9
+ 117	5
+ 958	4
+ 658	4
+ 623	5
+ 372	4
+ 859	7
+ 935	1
+ 823	9
+ 372	7
+ 488	4
+ 646	1
+ 982	1
+ 165	5
+ 412	4
+ 628	5
+ 382	7
+ 2	3
+ 135	7
+ 696	8
+ 179	1
+ 190	0
+ 730	1
+ 131	6
+ 36	5
+ 266	5
+ 857	9
+ 598	8
+ 19	8
+ 384	4
+ 209	0
+ 951	6
+ 759	10
+ 932	9
+ 612	6
+ 652	8
+ 696	8
+ 830	4
+ 966	10
+ 978	0
+ 464	2
+ 527	3
+ 155	1
+ 160	2
+ 889	5
+ 605	1
+ 556	6
+ 690	3
+ 508	6
+ 209	1
+ 249	9
+ 912	9
+ 703	7
+ 370	7
+ 703	3
+ 672	2
+ 591	2
+ 488	7
+ 324	6
+ 921	2
+ 191	5
+ 311	7
+ 82	0
+ 62	6
+ 621	3
+ 710	9
+ 132	6
+ 815	8
+ 364	2
+ 504	1
+ 533	2
+ 234	1
+ 374	7
+ 872	7
+ 369	8
+ 911	6
+ 319	2
+ 307	4
+ 221	4
+ 990	8
+ 641	7
+ 713	8
+ 323	5
+ 608	7
+ 714	1
+ 755	2
+ 288	10
+ 372	7
+ 711	2
+ 360	1
+ 36	3
+ 640	4
+ 492	9
+ 755	7
+ 317	7
+ 556	10
+ 446	3
+ 731	8
+ 798	3
+ 457	5
+ 450	2
+ 760	7
+ 201	1
+ 400	9
+ 375	8
+ 991	4
+ 31	6
+ 765	5
+ 578	5
+ 237	9
+ 265	8
+ 852	7
+ 63	6
+ 481	9
+ 921	9
+ 374	4
+ 149	1
+ 109	3
+ 265	5
+ 261	6
+ 270	3
+ 50	3
+ 883	8
+ 824	5
+ 335	1
+ 355	6
+ 854	2
+ 312	9
+ 789	8
+ 778	7
+ 730	2
+ 81	9
+ 285	2
+ 228	6
+ 700	5
+ 190	10
+ 740	2
+ 271	6
+ 55	1
+ 84	4
+ 156	4
+ 990	0
+ 646	3
+ 927	4
+ 94	7
+ 145	8
+ 856	2
+ 702	1
+ 417	9
+ 692	1
+ 418	9
+ 87	2
+ 122	4
+ 782	2
+ 453	9
+ 567	6
+ 305	6
+ 619	10
+ 859	5
+ 386	10
+ 250	5
+ 776	1
+ 757	5
+ 249	2
+ 407	9
+ 291	8
+ 823	4
+ 983	9
+ 736	8
+ 121	2
+ 631	7
+ 798	9
+ 245	4
+ 886	1
+ 963	3
+ 57	2
+ 803	8
+ 320	6
+ 310	6
+ 734	7
+ 509	0
+ 543	3
+ 403	5
+ 276	1
+ 291	4
+ 328	9
+ 85	1
+ 858	3
+ 544	7
+ 434	5
+ 16	5
+ 719	8
+ 324	0
+ 378	6
+ 607	1
+ 352	1
+ 137	9
+ 447	5
+ 420	7
+ 679	7
+ 119	0
+ 634	2
+ 134	5
+ 535	7
+ 236	10
+ 184	3
+ 461	9
+ 71	8
+ 942	4
+ 418	5
+ 561	8
+ 664	7
+ 664	1
+ 238	1
+ 834	9
+ 796	10
+ 924	4
+ 158	1
+ 921	7
+ 735	2
+ 662	9
+ 409	1
+ 822	5
+ 907	8
+ 929	3
+ 312	5
+ 95	10
+ 188	8
+ 87	4
+ 844	9
+ 342	6
+ 874	3
+ 69	0
+ 324	10
+ 724	1
+ 148	4
+ 977	6
+ 510	8
+ 38	4
+ 563	10
+ 743	9
+ 458	8
+ 851	6
+ 598	9
+ 72	4
+ 859	4
+ 81	7
+ 680	2
+ 764	0
+ 141	5
+ 63	3
+ 875	0
+ 846	4
+ 839	9
+ 801	4
+ 851	5
+ 277	3
+ 382	1
+ 955	10
+ 65	0
+ 421	9
+ 441	5
+ 656	1
+ 653	4
+ 125	8
+ 908	2
+ 83	8
+ 228	9
+ 167	1
+ 813	10
+ 469	7
+ 513	7
+ 974	9
+ 873	9
+ 875	9
+ 955	3
+ 862	4
+ 799	5
+ 517	5
+ 939	6
+ 245	8
+ 830	3
+ 630	1
+ 257	8
+ 126	1
+ 765	6
+ 734	3
+ 341	7
+ 173	2
+ 637	0
+ 152	6
+ 344	0
+ 988	1
+ 533	5
+ 594	5
+ 148	8
+ 319	10
+ 166	9
+ 37	4
+ 745	2
+ 493	5
+ 757	2
+ 788	1
+ 935	10
+ 311	6
+ 9	5
+ 164	4
+ 478	2
+ 495	0
+ 658	1
+ 483	8
+ 927	8
+ 785	1
+ 751	8
+ 516	5
+ 984	0
+ 7	7
+ 235	8
+ 840	2
+ 756	2
+ 742	8
+ 615	9
+ 118	1
+ 58	6
+ 104	7
+ 700	6
+ 522	6
+ 389	3
+ 720	1
+ 128	2
+ 637	1
+ 244	6
+ 854	5
+ 439	7
+ 650	2
+ 845	4
+ 961	5
+ 298	1
+ 552	4
+ 690	7
+ 72	4
+ 243	6
+ 18	6
+ 901	7
+ 772	0
+ 973	4
+ 142	2
+ 52	10
+ 695	5
+ 691	3
+ 687	5
+ 737	6
+ 995	0
+ 725	5
+ 392	4
+ 203	5
+ 806	4
+ 59	8
+ 77	10
+ 562	8
+ 989	5
+ 258	1
+ 751	3
+ 127	4
+ 802	8
+ 792	5
+ 353	5
+ 136	3
+ 564	9
+ 895	10
+ 278	1
+ 420	1
+ 544	5
+ 908	6
+ 438	5
+ 471	4
+ 5	7
+ 558	8
+ 40	7
+ 203	8
+ 503	10
+ 331	9
+ 523	5
+ 205	1
+ 330	1
+ 42	6
+ 199	5
+ 692	7
+ 941	6
+ 363	4
+ 70	8
+ 806	1
+ 563	4
+ 831	6
+ 49	0
+ 445	6
+ 28	8
+ 408	6
+ 245	6
+ 638	6
+ 713	7
+ 182	9
+ 142	9
+ 654	1
+ 473	0
+ 463	5
+ 852	3
+ 619	4
+ 632	4
+ 18	7
+ 484	5
+ 233	5
+ 240	6
+ 63	5
+ 254	7
+ 59	10
+ 380	2
+ 880	5
+ 114	5
+ 606	6
+ 551	1
+ 131	4
+ 337	7
+ 818	10
+ 199	8
+ 650	7
+ 299	9
+ 195	5
+ 524	3
+ 23	8
+ 958	1
+ 746	3
+ 322	6
+ 860	4
+ 159	5
+ 23	7
+ 535	2
+ 114	9
+ 904	9
+ 842	1
+ 767	5
+ 786	1
+ 375	10
+ 604	9
+ 239	6
+ 678	2
+ 708	4
+ 534	0
+ 49	4
+ 466	2
+ 861	5
+ 919	4
+ 643	0
+ 269	5
+ 964	1
+ 650	7
+ 603	4
+ 797	10
+ 418	4
+ 877	7
+ 28	6
+ 853	7
+ 979	4
+ 766	0
+ 782	2
+ 236	6
+ 721	2
+ 40	4
+ 188	3
+ 911	2
+ 419	6
+ 884	0
+ 999	7
+ 1000	4
+ 82	9
+ 73	1
+ 432	9
+ 846	4
+ 313	6
+ 439	1
+ 844	7
+ 739	6
+ 831	8
+ 929	0
+ 87	8
+ 172	5
+ 402	1
+ 528	4
+ 736	5
+ 817	8
+ 405	9
+ 927	8
+ 817	8
+ 249	1
+ 384	7
+ 225	2
+ 364	10
+ 793	2
+ 742	7
+ 215	8
+ 562	4
+ 336	10
+ 443	9
+ 365	2
+ 392	2
+ 997	8
+ 72	9
+ 635	9
+ 697	9
+ 19	1
+ 573	2
+ 309	9
+ 208	1
+ 132	10
+ 824	3
+ 780	4
+ 734	1
+ 351	2
+ 980	7
+ 356	4
+ 897	4
+ 170	10
+ 276	8
+ 858	10
+ 690	9
+ 54	3
+ 121	4
+ 199	3
+ 466	3
+ 280	3
+ 678	1
+ 677	4
+ 175	0
+ 589	2
+ 743	9
+ 527	6
+ 297	7
+ 610	6
+ 502	5
+ 547	2
+ 345	6
+ 454	5
+ 965	7
+ 795	4
+ 983	1
+ 721	7
+ 135	4
+ 74	3
+ 425	7
+ 465	2
+ 607	10
+ 808	9
+ 689	4
+ 478	2
+ 886	0
+ 382	2
+ 626	8
+ 697	6
+ 488	5
+ 21	5
+ 567	7
+ 133	7
+ 140	2
+ 12	6
+ 869	5
+ 734	5
+ 469	5
+ 381	2
+ 960	9
+ 349	8
+ 884	7
+ 77	5
+ 567	8
+ 100	1
+ 266	1
+ 527	8
+ 864	7
+ 535	0
+ 867	5
+ 570	7
+ 24	3
+ 213	5
+ 845	6
+ 651	8
+ 453	0
+ 651	3
+ 732	7
+ 846	3
+ 501	9
+ 355	8
+ 67	9
+ 600	9
+ 542	1
+ 935	4
+ 682	5
+ 146	7
+ 808	4
+ 199	7
+ 953	9
+ 459	4
+ 851	1
+ 743	6
+ 837	6
+ 882	3
+ 534	2
+ 105	6
+ 118	7
+ 532	7
+ 840	5
+ 70	5
+ 971	2
+ 228	8
+ 575	4
+ 433	5
+ 277	9
+ 935	1
+ 1	7
+ 710	8
+ 266	6
+ 176	8
+ 828	3
+ 402	9
+ 986	9
+ 607	8
+ 399	7
+ 348	4
+ 892	6
+ 150	5
+ 1	6
+ 996	3
+ 474	9
+ 406	5
+ 609	1
+ 312	9
+ 708	5
+ 676	5
+ 768	1
+ 483	8
+ 10	1
+ 580	4
+ 766	9
+ 780	7
+ 502	9
+ 125	5
+ 513	1
+ 782	10
+ 52	2
+ 461	7
+ 304	8
+ 535	0
+ 261	2
+ 548	0
+ 288	0
+ 783	3
+ 121	4
+ 708	9
+ 290	5
+ 545	8
+ 418	7
+ 296	9
+ 791	1
+ 918	8
+ 266	4
+ 504	6
+ 153	0
+ 581	4
+ 250	1
+ 443	5
+ 161	2
+ 836	3
+ 589	5
+ 169	9
+ 32	7
+ 671	4
+ 384	10
+ 381	2
+ 45	3
+ 19	3
+ 678	5
+ 881	8
+ 561	5
+ 244	8
+ 591	7
+ 349	8
+ 913	2
+ 34	5
+ 728	2
+ 380	8
+ 916	1
+ 209	3
+ 18	6
+ 476	1
+ 890	5
+ 374	6
+ 17	3
+ 399	6
+ 716	6
+ 389	3
+ 330	7
+ 60	2
+ 922	1
+ 744	6
+ 296	1
+ 409	2
+ 174	6
+ 513	2
+ 209	10
+ 255	1
+ 483	6
+ 667	5
+ 883	1
+ 78	6
+ 708	5
+ 907	0
+ 204	10
+ 280	1
+ 60	0
+ 775	4
+ 147	2
+ 569	3
+ 803	1
+ 512	0
+ 71	8
+ 111	6
+ 396	8
+ 53	3
+ 842	1
+ 878	6
+ 597	8
+ 588	8
+ 751	9
+ 927	8
+ 891	7
+ 169	0
+ 886	7
+ 359	7
+ 820	9
+ 701	9
+ 638	8
+ 445	0
+ 588	5
+ 312	4
+ 628	2
+ 981	2
+ 975	6
+ 26	7
+ 437	10
+ 538	3
+ 655	7
+ 366	5
+ 445	7
+ 229	3
+ 595	9
+ 156	2
+ 741	6
+ 266	3
+ 98	6
+ 760	7
+ 768	7
+ 952	7
+ 310	10
+ 469	7
+ 931	0
+ 74	6
+ 713	4
+ 127	2
+ 164	4
+ 423	8
+ 286	6
+ 992	0
+ 180	3
+ 357	3
+ 837	1
+ 5	6
+ 858	10
+ 348	2
+ 935	8
+ 915	9
+ 823	10
+ 452	5
+ 429	6
+ 694	6
+ 935	1
+ 352	2
+ 696	3
+ 249	9
+ 602	6
+ 153	4
+ 722	2
+ 44	6
+ 115	4
+ 748	0
+ 208	7
+ 915	0
+ 652	4
+ 566	1
+ 946	3
+ 673	9
+ 377	0
+ 102	1
+ 369	4
+ 948	10
+ 956	1
+ 409	7
+ 259	5
+ 258	4
+ 844	0
+ 423	1
+ 669	3
+ 82	3
+ 705	6
+ 402	7
+ 908	1
+ 533	3
+ 101	6
+ 357	5
+ 986	3
+ 440	9
+ 406	8
+ 620	7
+ 303	9
+ 39	1
+ 885	5
+ 199	6
+ 801	3
+ 875	5
+ 929	3
+ 157	8
+ 353	7
+ 123	5
+ 325	5
+ 923	3
+ 785	4
+ 252	2
+ 213	9
+ 857	5
+ 751	9
+ 663	6
+ 359	9
+ 190	2
+ 142	1
+ 665	1
+ 343	8
+ 909	7
+ 513	0
+ 149	8
+ 513	1
+ 148	3
+ 435	4
+ 489	6
+ 273	3
+ 163	0
+ 243	8
+ 660	6
+ 687	8
+ 761	8
+ 914	4
+ 901	3
+ 249	8
+ 952	8
+ 843	1
+ 600	4
+ 173	7
+ 653	6
+ 149	1
+ 255	4
+ 489	4
+ 446	7
+ 244	1
+ 334	9
+ 955	1
+ 760	9
+ 521	7
+ 126	8
+ 471	1
+ 532	3
+ 180	1
+ 668	4
+ 880	3
+ 961	0
+ 464	2
+ 450	10
+ 634	9
+ 685	9
+ 2	0
+ 809	10
+ 113	6
+ 826	6
+ 230	10
+ 405	7
+ 30	9
+ 14	2
+ 69	7
+ 563	9
+ 3	5
+ 978	5
+ 740	4
+ 420	4
+ 324	1
+ 252	3
+ 123	1
+ 283	2
+ 631	1
+ 871	9
+ 60	3
+ 561	1
+ 213	6
+ 301	3
+ 257	9
+ 232	3
+ 388	2
+ 727	1
+ 637	1
+ 501	10
+ 252	8
+ 288	4
+ 815	6
+ 612	4
+ 678	5
+ 306	7
+ 759	9
+ 829	10
+ 442	1
+ 255	7
+ 994	5
+ 959	4
+ 696	7
+ 509	3
+ 833	0
+ 294	1
+ 764	6
+ 461	6
+ 152	1
+ 25	8
+ 555	3
+ 569	3
+ 199	4
+ 287	6
+ 528	5
+ 339	5
+ 28	3
+ 903	7
+ 983	4
+ 57	8
+ 422	4
+ 902	2
+ 933	4
+ 765	1
+ 435	8
+ 915	10
+ 122	5
+ 304	3
+ 882	6
+ 961	4
+ 133	3
+ 931	2
+ 598	8
+ 885	6
+ 246	9
+ 397	7
+ 292	3
+ 853	2
+ 662	6
+ 310	1
+ 409	2
+ 86	5
+ 709	4
+ 852	6
+ 982	8
+ 1	1
+ 114	9
+ 276	7
+ 766	2
+ 293	0
+ 102	7
+ 680	4
+ 989	5
+ 620	7
+ 152	9
+ 747	6
+ 154	8
+ 92	9
+ 224	9
+ 454	2
+ 758	5
+ 321	9
+ 386	6
+ 584	2
+ 758	9
+ 164	9
+ 567	8
+ 255	6
+ 377	9
+ 207	5
+ 804	10
+ 89	10
+ 788	2
+ 821	0
+ 126	3
+ 218	9
+ 729	5
+ 757	1
+ 136	3
+ 267	9
+ 219	4
+ 755	8
+ 275	0
+ 342	7
+ 885	5
+ 179	7
+ 503	3
+ 648	3
+ 450	5
+ 303	6
+ 743	5
+ 460	5
+ 60	2
+ 587	2
+ 559	9
+ 91	8
+ 285	8
+ 563	6
+ 856	9
+ 211	7
+ 454	4
+ 430	10
+ 659	1
+ 249	1
+ 546	6
+ 685	3
+ 72	1
+ 762	1
+ 363	3
+ 328	9
+ 202	4
+ 699	5
+ 265	3
+ 47	1
+ 168	3
+ 862	6
+ 649	3
+ 580	3
+ 369	8
+ 417	9
+ 379	1
+ 205	5
+ 247	10
+ 583	6
+ 315	9
+ 532	5
+ 331	2
+ 5	6
+ 493	1
+ 717	7
+ 310	6
+ 283	10
+ 870	9
+ 267	2
+ 691	7
+ 154	1
+ 786	4
+ 522	0
+ 326	1
+ 642	6
+ 17	2
+ 158	3
+ 405	2
+ 943	9
+ 215	7
+ 559	5
+ 238	8
+ 484	1
+ 704	8
+ 346	4
+ 435	5
+ 465	2
+ 860	10
+ 253	2
+ 92	9
+ 826	1
+ 70	10
+ 456	5
+ 147	4
+ 373	4
+ 60	9
+ 887	3
+ 774	4
+ 405	5
+ 122	8
+ 873	6
+ 253	3
+ 778	1
+ 326	0
+ 298	4
+ 927	1
+ 527	10
+ 109	10
+ 471	3
+ 383	8
+ 618	4
+ 775	5
+ 740	5
+ 875	1
+ 27	10
+ 897	9
+ 554	1
+ 239	3
+ 263	6
+ 362	6
+ 982	3
+ 686	5
+ 285	8
+ 492	8
+ 51	9
+ 600	7
+ 317	4
+ 173	1
+ 924	0
+ 203	10
+ 45	1
+ 851	6
+ 250	1
+ 930	5
+ 654	3
+ 74	6
+ 581	8
+ 145	9
+ 554	6
+ 623	6
+ 511	2
+ 274	8
+ 598	4
+ 886	5
+ 496	1
+ 474	5
+ 189	3
+ 141	4
+ 414	1
+ 953	1
+ 363	0
+ 704	9
+ 786	8
+ 811	3
+ 485	4
+ 946	10
+ 657	2
+ 825	3
+ 668	7
+ 778	2
+ 800	3
+ 705	10
+ 576	8
+ 429	10
+ 916	4
+ 58	3
+ 409	8
+ 225	2
+ 610	0
+ 536	1
+ 470	5
+ 92	1
+ 702	9
+ 383	4
+ 628	2
+ 533	4
+ 412	2
+ 417	10
+ 84	8
+ 978	0
+ 229	0
+ 280	6
+ 798	5
+ 834	4
+ 540	4
+ 504	0
+ 852	6
+ 138	6
+ 512	5
+ 925	1
+ 682	5
+ 567	1
+ 696	10
+ 82	8
+ 830	1
+ 780	1
+ 96	1
+ 697	9
+ 565	5
+ 302	1
+ 900	8
+ 116	8
+ 401	3
+ 307	9
+ 774	2
+ 52	5
+ 690	6
+ 550	4
+ 603	6
+ 166	4
+ 691	9
+ 493	8
+ 7	2
+ 681	6
+ 720	10
+ 677	6
+ 789	8
+ 374	2
+ 46	7
+ 103	8
+ 913	2
+ 276	6
+ 774	8
+ 989	4
+ 457	2
+ 811	1
+ 102	3
+ 935	1
+ 493	6
+ 680	2
+ 601	4
+ 835	4
+ 149	2
+ 580	2
+ 889	7
+ 14	8
+ 838	3
+ 404	6
+ 115	4
+ 989	6
+ 548	8
+ 720	6
+ 103	7
+ 758	6
+ 272	4
+ 810	9
+ 795	6
+ 262	9
+ 852	8
+ 138	7
+ 525	2
+ 543	4
+ 442	9
+ 975	6
+ 340	10
+ 129	9
+ 764	8
+ 537	9
+ 504	3
+ 463	8
+ 733	3
+ 649	5
+ 916	9
+ 471	8
+ 754	6
+ 510	3
+ 761	1
+ 642	2
+ 1000	6
+ 761	3
+ 581	9
+ 227	3
+ 740	8
+ 211	2
+ 58	7
+ 21	8
+ 946	7
+ 318	9
+ 582	8
+ 631	3
+ 398	1
+ 615	2
+ 194	3
+ 363	2
+ 875	1
+ 533	5
+ 16	8
+ 801	8
+ 522	0
+ 0	6
+ 686	0
+ 371	6
+ 692	7
+ 494	3
+ 478	1
+ 610	9
+ 266	2
+ 36	5
+ 483	4
+ 653	4
+ 524	2
+ 814	5
+ 945	6
+ 296	5
+ 627	3
+ 47	3
+ 318	4
+ 944	0
+ 108	4
+ 283	6
+ 564	9
+ 463	8
+ 118	5
+ 290	6
+ 898	9
+ 959	4
+ 129	8
+ 963	1
+ 388	3
+ 541	0
+ 555	6
+ 327	9
+ 6	3
+ 882	1
+ 711	2
+ 700	3
+ 58	2
+ 105	2
+ 662	4
+ 777	6
+ 338	7
+ 983	5
+ 509	9
+ 540	9
+ 205	1
+ 912	8
+ 669	2
+ 633	7
+ 511	5
+ 790	2
+ 680	5
+ 496	7
+ 653	6
+ 915	3
+ 995	7
+ 875	3
+ 429	9
+ 800	9
+ 804	3
+ 835	0
+ 422	7
+ 768	1
+ 987	4
+ 767	5
+ 915	6
+ 720	6
+ 47	2
+ 334	7
+ 817	2
+ 15	8
+ 941	9
+ 145	4
+ 747	9
+ 307	6
+ 286	1
+ 559	7
+ 890	3
+ 798	9
+ 727	6
+ 375	6
+ 122	1
+ 238	2
+ 311	6
+ 869	1
+ 820	9
+ 941	8
+ 773	1
+ 130	5
+ 31	4
+ 70	3
+ 580	6
+ 24	5
+ 956	8
+ 347	7
+ 387	7
+ 325	5
+ 817	6
+ 678	1
+ 134	5
+ 257	10
+ 431	2
+ 715	2
+ 284	8
+ 724	3
+ 281	8
+ 632	9
+ 423	7
+ 331	4
+ 477	7
+ 62	9
+ 400	4
+ 374	2
+ 950	1
+ 346	1
+ 599	6
+ 38	0
+ 800	8
+ 234	1
+ 597	10
+ 399	9
+ 751	0
+ 740	2
+ 686	1
+ 554	2
+ 749	6
+ 28	1
+ 2	4
+ 366	10
+ 454	7
+ 36	1
+ 314	1
+ 83	1
+ 827	3
+ 198	4
+ 275	6
+ 304	0
+ 628	0
+ 201	3
+ 114	8
+ 477	9
+ 370	5
+ 12	4
+ 907	4
+ 324	4
+ 89	4
+ 414	4
+ 435	5
+ 517	3
+ 815	7
+ 687	1
+ 313	10
+ 116	9
+ 34	3
+ 255	1
+ 71	7
+ 12	4
+ 237	0
+ 812	1
+ 401	1
+ 505	5
+ 496	9
+ 893	9
+ 417	4
+ 193	2
+ 125	9
+ 321	4
+ 871	4
+ 380	9
+ 753	6
+ 53	8
+ 366	1
+ 264	6
+ 88	1
+ 747	5
+ 213	3
+ 979	7
+ 171	9
+ 640	6
+ 281	8
+ 819	4
+ 714	1
+ 845	6
+ 577	2
+ 489	3
+ 859	5
+ 154	2
+ 607	4
+ 828	7
+ 495	6
+ 184	7
+ 827	2
+ 417	10
+ 34	1
+ 586	3
+ 890	4
+ 721	6
+ 545	6
+ 188	1
+ 791	7
+ 452	7
+ 219	6
+ 875	8
+ 25	7
+ 521	5
+ 279	7
+ 228	1
+ 868	6
+ 105	9
+ 701	7
+ 217	6
+ 96	9
+ 196	6
+ 505	4
+ 763	3
+ 61	2
+ 946	3
+ 823	8
+ 107	8
+ 525	6
+ 368	8
+ 333	6
+ 910	2
+ 240	0
+ 103	9
+ 706	3
+ 533	8
+ 258	7
+ 443	8
+ 112	2
+ 58	2
+ 423	0
+ 455	2
+ 825	6
+ 93	4
+ 190	5
+ 154	5
+ 56	1
+ 725	3
+ 79	8
+ 237	8
+ 147	8
+ 587	4
+ 498	0
+ 167	6
+ 236	2
+ 785	7
+ 230	2
+ 904	1
+ 801	10
+ 405	10
+ 458	6
+ 515	5
+ 623	2
+ 810	7
+ 67	0
+ 486	2
+ 817	1
+ 619	3
+ 102	8
+ 926	3
+ 11	7
+ 998	2
+ 950	9
+ 297	8
+ 899	7
+ 743	4
+ 261	3
+ 871	9
+ 498	7
+ 585	6
+ 728	1
+ 779	5
+ 144	4
+ 861	2
+ 183	8
+ 585	2
+ 498	6
+ 436	4
+ 485	7
+ 200	4
+ 434	9
+ 741	7
+ 202	6
+ 578	7
+ 293	2
+ 264	0
+ 234	0
+ 566	4
+ 440	4
+ 624	6
+ 213	2
+ 817	7
+ 791	3
+ 160	3
+ 984	4
+ 660	4
+ 303	4
+ 113	5
+ 13	7
+ 204	3
+ 855	5
+ 326	1
+ 511	9
+ 467	10
+ 318	1
+ 573	5
+ 300	4
+ 242	1
+ 642	4
+ 367	6
+ 762	0
+ 45	1
+ 428	2
+ 570	4
+ 851	8
+ 746	7
+ 243	1
+ 795	8
+ 963	3
+ 705	3
+ 354	3
+ 811	7
+ 668	1
+ 744	3
+ 456	1
+ 937	2
+ 137	10
+ 283	6
+ 140	9
+ 5	10
+ 628	8
+ 697	9
+ 823	5
+ 626	8
+ 755	3
+ 66	1
+ 609	9
+ 762	3
+ 931	5
+ 586	4
+ 616	5
+ 604	8
+ 505	9
+ 318	6
+ 741	3
+ 636	4
+ 74	3
+ 241	9
+ 825	9
+ 683	6
+ 197	7
+ 688	8
+ 626	5
+ 82	6
+ 956	7
+ 944	6
+ 192	5
+ 325	7
+ 436	6
+ 342	2
+ 965	10
+ 547	0
+ 312	8
+ 936	1
+ 654	6
+ 717	9
+ 368	4
+ 658	10
+ 855	7
+ 551	8
+ 409	5
+ 382	6
+ 44	7
+ 298	5
+ 349	6
+ 658	3
+ 619	2
+ 354	9
+ 992	3
+ 67	6
+ 909	8
+ 498	3
+ 188	2
+ 271	0
+ 895	8
+ 854	3
+ 318	2
+ 905	4
+ 943	2
+ 843	3
+ 843	5
+ 607	5
+ 705	10
+ 392	7
+ 251	5
+ 343	2
+ 242	8
+ 437	4
+ 995	7
+ 474	9
+ 530	3
+ 195	8
+ 565	1
+ 210	5
+ 303	1
+ 800	1
+ 553	4
+ 609	3
+ 368	0
+ 955	6
+ 460	3
+ 780	7
+ 138	2
+ 133	1
+ 926	6
+ 24	5
+ 935	2
+ 304	5
+ 318	5
+ 8	6
+ 568	8
+ 768	1
+ 216	4
+ 379	6
+ 377	3
+ 204	8
+ 631	10
+ 539	8
+ 202	7
+ 901	1
+ 279	9
+ 584	2
+ 143	9
+ 714	5
+ 403	7
+ 83	10
+ 530	9
+ 92	7
+ 228	5
+ 331	6
+ 804	5
+ 442	4
+ 520	10
+ 203	7
+ 652	1
+ 850	9
+ 29	4
+ 145	2
+ 323	9
+ 633	7
+ 581	7
+ 696	1
+ 567	8
+ 857	8
+ 259	2
+ 400	1
+ 723	8
+ 498	2
+ 822	7
+ 965	5
+ 804	8
+ 405	8
+ 249	6
+ 5	6
+ 409	6
+ 297	10
+ 354	10
+ 100	9
+ 782	10
+ 716	0
+ 146	1
+ 104	9
+ 958	6
+ 112	8
+ 302	1
+ 255	1
+ 892	7
+ 939	1
+ 211	9
+ 713	6
+ 582	0
+ 609	9
+ 4	7
+ 857	8
+ 667	6
+ 828	8
+ 690	9
+ 683	6
+ 533	8
+ 428	8
+ 873	7
+ 942	8
+ 344	9
+ 907	6
+ 825	6
+ 174	4
+ 630	8
+ 343	6
+ 492	2
+ 421	2
+ 774	2
+ 972	5
+ 180	7
+ 112	7
+ 450	5
+ 549	3
+ 224	5
+ 88	6
+ 372	10
+ 122	2
+ 614	3
+ 604	2
+ 77	9
+ 880	6
+ 148	3
+ 728	9
+ 550	7
+ 386	7
+ 354	5
+ 444	8
+ 38	10
+ 127	3
+ 484	2
+ 829	9
+ 209	10
+ 53	8
+ 245	7
+ 68	3
+ 605	9
+ 892	8
+ 249	6
+ 674	8
+ 319	1
+ 529	7
+ 558	10
+ 478	6
+ 967	6
+ 858	5
+ 820	7
+ 307	0
+ 637	4
+ 852	9
+ 19	9
+ 205	6
+ 869	1
+ 376	1
+ 717	1
+ 917	0
+ 111	4
+ 709	7
+ 420	2
+ 265	4
+ 792	1
+ 838	6
+ 809	1
+ 640	4
+ 506	5
+ 328	5
+ 414	5
+ 148	3
+ 630	5
+ 400	3
+ 576	3
+ 382	7
+ 764	1
+ 356	2
+ 279	6
+ 571	1
+ 743	4
+ 683	6
+ 554	3
+ 998	1
+ 816	3
+ 585	2
+ 858	7
+ 512	5
+ 258	9
+ 835	8
+ 230	2
+ 520	10
+ 308	9
+ 177	6
+ 497	7
+ 659	2
+ 157	3
+ 793	7
+ 665	8
+ 772	5
+ 116	4
+ 711	10
+ 90	2
+ 463	3
+ 136	3
+ 181	4
+ 514	7
+ 359	8
+ 577	5
+ 410	1
+ 285	1
+ 314	4
+ 411	1
+ 153	1
+ 897	9
+ 557	0
+ 281	3
+ 988	4
+ 492	5
+ 719	6
+ 748	9
+ 993	3
+ 601	4
+ 85	2
+ 889	5
+ 251	2
+ 564	6
+ 616	10
+ 672	8
+ 50	6
+ 694	6
+ 582	10
+ 875	6
+ 346	4
+ 21	1
+ 994	8
+ 964	10
+ 31	6
+ 340	1
+ 742	2
+ 610	10
+ 402	2
+ 559	0
+ 148	2
+ 786	2
+ 800	5
+ 805	4
+ 455	7
+ 952	8
+ 48	10
+ 866	0
+ 741	8
+ 29	8
+ 395	4
+ 887	1
+ 597	5
+ 132	10
+ 670	7
+ 17	8
+ 921	8
+ 17	7
+ 283	8
+ 103	7
+ 503	1
+ 541	6
+ 27	4
+ 592	8
+ 238	6
+ 539	6
+ 990	4
+ 771	6
+ 922	9
+ 586	6
+ 593	6
+ 411	5
+ 406	4
+ 235	7
+ 250	3
+ 428	8
+ 393	10
+ 303	4
+ 376	9
+ 188	6
+ 516	7
+ 246	5
+ 153	0
+ 93	1
+ 919	7
+ 667	5
+ 282	1
+ 27	7
+ 506	3
+ 378	8
+ 600	8
+ 509	10
+ 775	8
+ 414	2
+ 707	6
+ 765	2
+ 328	0
+ 729	5
+ 28	8
+ 556	9
+ 501	2
+ 460	8
+ 301	5
+ 471	8
+ 749	8
+ 563	3
+ 655	1
+ 342	4
+ 883	8
+ 582	6
+ 357	3
+ 813	7
+ 357	5
+ 166	4
+ 364	7
+ 333	9
+ 945	8
+ 649	2
+ 280	1
+ 53	0
+ 969	6
+ 377	6
+ 688	7
+ 55	6
+ 476	6
+ 161	8
+ 983	10
+ 519	3
+ 516	7
+ 726	9
+ 407	1
+ 745	4
+ 853	4
+ 598	1
+ 514	7
+ 161	5
+ 268	5
+ 107	10
+ 258	2
+ 527	7
+ 799	7
+ 567	8
+ 663	1
+ 123	2
+ 772	8
+ 59	2
+ 909	8
+ 532	8
+ 197	1
+ 894	7
+ 781	1
+ 193	0
+ 593	3
+ 5	9
+ 463	5
+ 585	3
+ 221	2
+ 45	9
+ 238	2
+ 63	0
+ 18	1
+ 189	9
+ 925	7
+ 688	1
+ 851	6
+ 833	6
+ 636	0
+ 681	2
+ 327	7
+ 80	8
+ 217	7
+ 53	4
+ 817	1
+ 322	1
+ 266	4
+ 66	3
+ 506	3
+ 210	4
+ 976	9
+ 554	8
+ 480	4
+ 458	1
+ 414	1
+ 345	7
+ 824	4
+ 532	0
+ 90	6
+ 480	9
+ 683	8
+ 963	9
+ 187	0
+ 234	7
+ 284	4
+ 124	3
+ 342	7
+ 87	8
+ 66	5
+ 938	5
+ 683	3
+ 221	5
+ 708	8
+ 548	8
+ 338	0
+ 706	0
+ 830	7
+ 971	0
+ 699	2
+ 709	10
+ 649	8
+ 244	10
+ 511	3
+ 813	6
+ 875	8
+ 57	6
+ 34	3
+ 66	7
+ 30	6
+ 541	4
+ 642	2
+ 390	5
+ 917	4
+ 487	6
+ 565	2
+ 600	2
+ 29	8
+ 205	5
+ 174	0
+ 118	0
+ 769	2
+ 608	8
+ 452	7
+ 545	5
+ 288	1
+ 851	9
+ 333	2
+ 401	3
+ 601	9
+ 867	2
+ 84	5
+ 380	1
+ 311	6
+ 654	5
+ 604	8
+ 535	4
+ 947	1
+ 176	4
+ 817	7
+ 881	1
+ 808	7
+ 34	1
+ 972	4
+ 392	6
+ 322	3
+ 740	4
+ 725	1
+ 520	0
+ 706	2
+ 521	3
+ 947	1
+ 683	9
+ 199	9
+ 292	0
+ 581	2
+ 120	4
+ 905	2
+ 529	9
+ 588	9
+ 450	9
+ 179	2
+ 318	9
+ 310	8
+ 941	0
+ 13	5
+ 325	10
+ 518	0
+ 853	7
+ 867	1
+ 732	4
+ 318	9
+ 836	2
+ 6	4
+ 100	6
+ 287	6
+ 505	5
+ 741	8
+ 370	1
+ 661	3
+ 67	7
+ 773	4
+ 633	3
+ 401	5
+ 7	3
+ 631	7
+ 716	9
+ 592	6
+ 173	6
+ 917	3
+ 192	2
+ 824	7
+ 670	6
+ 520	0
+ 616	2
+ 351	7
+ 854	1
+ 75	5
+ 414	5
+ 973	4
+ 744	6
+ 160	5
+ 554	8
+ 11	7
+ 349	9
+ 0	5
+ 132	8
+ 239	8
+ 389	8
+ 842	0
+ 941	2
+ 688	8
+ 317	8
+ 282	7
+ 239	3
+ 151	10
+ 860	3
+ 441	4
+ 62	5
+ 141	4
+ 381	1
+ 952	5
+ 965	2
+ 315	4
+ 950	2
+ 359	9
+ 351	0
+ 686	7
+ 809	10
+ 397	0
+ 224	5
+ 30	1
+ 859	5
+ 497	9
+ 924	6
+ 331	3
+ 779	3
+ 818	7
+ 474	1
+ 99	4
+ 291	5
+ 316	6
+ 504	0
+ 308	3
+ 970	7
+ 361	2
+ 254	4
+ 277	1
+ 863	8
+ 33	8
+ 413	4
+ 93	2
+ 648	9
+ 937	1
+ 44	0
+ 546	3
+ 493	9
+ 976	10
+ 863	3
+ 310	8
+ 991	7
+ 27	2
+ 63	3
+ 358	9
+ 78	4
+ 714	5
+ 755	8
+ 682	4
+ 717	6
+ 525	8
+ 654	1
+ 97	1
+ 933	1
+ 144	8
+ 358	5
+ 629	3
+ 126	7
+ 593	2
+ 959	10
+ 115	0
+ 342	8
+ 527	1
+ 635	2
+ 501	4
+ 828	0
+ 114	5
+ 96	2
+ 630	0
+ 284	8
+ 825	6
+ 228	5
+ 990	4
+ 109	6
+ 542	1
+ 534	7
+ 105	9
+ 485	6
+ 974	1
+ 842	5
+ 473	7
+ 500	6
+ 152	6
+ 798	8
+ 625	1
+ 555	4
+ 723	8
+ 903	7
+ 136	0
+ 296	7
+ 80	8
+ 334	2
+ 706	8
+ 818	7
+ 940	7
+ 154	4
+ 329	7
+ 1000	5
+ 249	8
+ 264	9
+ 879	8
+ 323	6
+ 602	2
+ 314	7
+ 239	6
+ 416	3
+ 439	7
+ 505	1
+ 569	3
+ 825	5
+ 982	10
+ 921	3
+ 633	9
+ 793	9
+ 718	1
+ 756	6
+ 877	1
+ 198	5
+ 306	5
+ 217	5
+ 121	6
+ 864	6
+ 382	4
+ 706	10
+ 691	5
+ 460	7
+ 511	4
+ 985	1
+ 302	8
+ 26	0
+ 835	8
+ 617	7
+ 862	8
+ 191	2
+ 326	4
+ 713	4
+ 41	6
+ 8	4
+ 946	7
+ 375	6
+ 245	8
+ 310	8
+ 216	3
+ 900	5
+ 73	9
+ 538	9
+ 708	2
+ 620	6
+ 970	8
+ 738	3
+ 219	5
+ 743	3
+ 28	8
+ 683	10
+ 465	1
+ 611	7
+ 893	9
+ 466	1
+ 215	4
+ 626	3
+ 291	2
+ 196	10
+ 319	8
+ 569	3
+ 627	3
+ 585	8
+ 758	3
+ 107	8
+ 80	8
+ 759	5
+ 848	4
+ 255	7
+ 291	7
+ 849	5
+ 87	5
+ 794	4
+ 640	10
+ 378	10
+ 807	9
+ 249	4
+ 253	8
+ 281	0
+ 162	4
+ 797	2
+ 177	6
+ 787	0
+ 926	0
+ 766	2
+ 763	6
+ 723	9
+ 92	5
+ 228	7
+ 507	6
+ 692	3
+ 552	9
+ 748	8
+ 775	0
+ 817	9
+ 417	6
+ 179	6
+ 170	10
+ 619	1
+ 7	4
+ 312	8
+ 1	0
+ 621	1
+ 552	8
+ 825	1
+ 455	5
+ 373	0
+ 457	1
+ 813	2
+ 151	6
+ 169	6
+ 243	3
+ 161	4
+ 314	8
+ 508	3
+ 166	8
+ 92	2
+ 856	7
+ 259	4
+ 561	1
+ 467	0
+ 600	8
+ 24	1
+ 961	8
+ 289	1
+ 467	5
+ 679	7
+ 806	8
+ 124	1
+ 621	6
+ 441	8
+ 453	5
+ 954	3
+ 245	2
+ 716	8
+ 297	2
+ 823	9
+ 22	8
+ 955	10
+ 684	2
+ 95	2
+ 702	8
+ 862	5
+ 615	10
+ 628	2
+ 617	1
+ 23	1
+ 602	10
+ 378	8
+ 189	1
+ 654	5
+ 276	5
+ 383	3
+ 323	3
+ 281	0
+ 582	4
+ 159	3
+ 151	0
+ 793	8
+ 6	4
+ 2	6
+ 491	0
+ 693	1
+ 2	1
+ 941	2
+ 164	6
+ 677	4
+ 71	1
+ 737	4
+ 398	0
+ 402	10
+ 395	6
+ 264	5
+ 581	1
+ 312	6
+ 477	3
+ 209	10
+ 340	9
+ 61	3
+ 972	0
+ 532	1
+ 596	2
+ 576	7
+ 269	3
+ 61	7
+ 331	5
+ 647	7
+ 23	9
+ 272	6
+ 967	6
+ 190	4
+ 899	4
+ 413	2
+ 300	5
+ 581	3
+ 475	1
+ 408	1
+ 323	10
+ 738	6
+ 297	8
+ 259	6
+ 262	9
+ 354	3
+ 817	6
+ 890	8
+ 211	1
+ 230	1
+ 479	6
+ 350	8
+ 116	9
+ 52	6
+ 44	5
+ 662	4
+ 443	4
+ 959	7
+ 200	2
+ 368	5
+ 124	7
+ 748	9
+ 349	6
+ 727	6
+ 718	10
+ 671	2
+ 599	0
+ 977	7
+ 952	0
+ 307	10
+ 488	10
+ 363	9
+ 369	3
+ 672	6
+ 540	0
+ 31	7
+ 763	8
+ 606	1
+ 417	3
+ 672	1
+ 289	3
+ 333	9
+ 364	3
+ 604	3
+ 339	9
+ 311	8
+ 879	7
+ 759	2
+ 996	4
+ 817	5
+ 471	8
+ 199	2
+ 627	8
+ 346	0
+ 138	0
+ 180	4
+ 362	5
+ 316	7
+ 823	9
+ 41	2
+ 830	4
+ 989	7
+ 26	7
+ 957	0
+ 179	8
+ 557	7
+ 622	8
+ 885	2
+ 562	2
+ 294	7
+ 250	5
+ 128	6
+ 987	4
+ 337	8
+ 363	4
+ 972	2
+ 730	10
+ 901	8
+ 710	9
+ 777	9
+ 632	3
+ 540	3
+ 91	4
+ 503	7
+ 656	8
+ 353	9
+ 271	5
+ 517	3
+ 924	9
+ 68	3
+ 232	0
+ 480	10
+ 2	4
+ 717	7
+ 240	5
+ 600	9
+ 829	1
+ 126	9
+ 564	6
+ 573	2
+ 426	9
+ 126	7
+ 406	6
+ 955	3
+ 498	0
+ 618	7
+ 62	1
+ 692	1
+ 481	4
+ 775	7
+ 904	4
+ 592	7
+ 515	7
+ 652	1
+ 347	2
+ 300	8
+ 150	4
+ 471	6
+ 69	4
+ 887	6
+ 448	5
+ 297	5
+ 605	10
+ 574	1
+ 398	3
+ 806	3
+ 725	4
+ 34	2
+ 116	7
+ 320	5
+ 911	6
+ 237	1
+ 46	7
+ 619	1
+ 133	5
+ 682	6
+ 12	10
+ 91	6
+ 967	7
+ 702	4
+ 14	5
+ 667	7
+ 905	7
+ 978	0
+ 387	3
+ 484	3
+ 918	7
+ 361	10
+ 429	10
+ 78	6
+ 485	8
+ 143	5
+ 738	2
+ 113	7
+ 899	8
+ 70	9
+ 322	7
+ 651	2
+ 438	6
+ 247	8
+ 927	7
+ 124	8
+ 453	5
+ 808	9
+ 464	9
+ 445	9
+ 646	6
+ 446	4
+ 822	6
+ 89	7
+ 374	2
+ 633	7
+ 897	3
+ 923	3
+ 913	2
+ 160	8
+ 902	3
+ 684	4
+ 768	5
+ 237	2
+ 378	7
+ 181	0
+ 270	6
+ 408	1
+ 187	5
+ 814	6
+ 657	4
+ 257	6
+ 731	2
+ 889	6
+ 350	0
+ 484	3
+ 333	2
+ 607	1
+ 661	8
+ 333	0
+ 527	5
+ 63	8
+ 142	5
+ 890	3
+ 968	7
+ 889	6
+ 151	1
+ 179	9
+ 325	1
+ 526	7
+ 116	0
+ 927	4
+ 178	5
+ 550	8
+ 379	9
+ 877	9
+ 398	9
+ 703	5
+ 410	6
+ 868	4
+ 297	8
+ 3	4
+ 903	2
+ 329	2
+ 250	9
+ 903	4
+ 865	8
+ 815	0
+ 366	4
+ 881	7
+ 248	8
+ 651	6
+ 698	4
+ 185	1
+ 947	1
+ 487	2
+ 810	5
+ 691	7
+ 672	0
+ 940	9
+ 875	8
+ 287	7
diff --git a/contrib/bloom/expected/bloom.out b/contrib/bloom/expected/bloom.out
new file mode 100644
index ...f7334fa
*** a/contrib/bloom/expected/bloom.out
--- b/contrib/bloom/expected/bloom.out
***************
*** 0 ****
--- 1,120 ----
+ CREATE EXTENSION bloom;
+ CREATE TABLE tst (
+ 	i	int4,
+ 	t	text
+ );
+ \copy tst from 'data/data'
+ CREATE INDEX bloomidx ON tst USING bloom (i, t) WITH (col1 = 3);
+ SET enable_seqscan=on;
+ SET enable_bitmapscan=off;
+ SET enable_indexscan=off;
+ SELECT count(*) FROM tst WHERE i = 16;
+  count 
+ -------
+     14
+ (1 row)
+ 
+ SELECT count(*) FROM tst WHERE t = '5';
+  count 
+ -------
+   1008
+ (1 row)
+ 
+ SELECT count(*) FROM tst WHERE i = 16 AND t = '5';
+  count 
+ -------
+      4
+ (1 row)
+ 
+ SET enable_seqscan=off;
+ SET enable_bitmapscan=on;
+ SET enable_indexscan=on;
+ EXPLAIN (COSTS OFF) SELECT count(*) FROM tst WHERE i = 16;
+                 QUERY PLAN                 
+ -------------------------------------------
+  Aggregate
+    ->  Bitmap Heap Scan on tst
+          Recheck Cond: (i = 16)
+          ->  Bitmap Index Scan on bloomidx
+                Index Cond: (i = 16)
+ (5 rows)
+ 
+ EXPLAIN (COSTS OFF) SELECT count(*) FROM tst WHERE t = '5';
+                 QUERY PLAN                 
+ -------------------------------------------
+  Aggregate
+    ->  Bitmap Heap Scan on tst
+          Recheck Cond: (t = '5'::text)
+          ->  Bitmap Index Scan on bloomidx
+                Index Cond: (t = '5'::text)
+ (5 rows)
+ 
+ EXPLAIN (COSTS OFF) SELECT count(*) FROM tst WHERE i = 16 AND t = '5';
+                         QUERY PLAN                        
+ ----------------------------------------------------------
+  Aggregate
+    ->  Bitmap Heap Scan on tst
+          Recheck Cond: ((i = 16) AND (t = '5'::text))
+          ->  Bitmap Index Scan on bloomidx
+                Index Cond: ((i = 16) AND (t = '5'::text))
+ (5 rows)
+ 
+ SELECT count(*) FROM tst WHERE i = 16;
+  count 
+ -------
+     14
+ (1 row)
+ 
+ SELECT count(*) FROM tst WHERE t = '5';
+  count 
+ -------
+   1008
+ (1 row)
+ 
+ SELECT count(*) FROM tst WHERE i = 16 AND t = '5';
+  count 
+ -------
+      4
+ (1 row)
+ 
+ VACUUM ANALYZE tst;
+ SELECT count(*) FROM tst WHERE i = 16;
+  count 
+ -------
+     14
+ (1 row)
+ 
+ SELECT count(*) FROM tst WHERE t = '5';
+  count 
+ -------
+   1008
+ (1 row)
+ 
+ SELECT count(*) FROM tst WHERE i = 16 AND t = '5';
+  count 
+ -------
+      4
+ (1 row)
+ 
+ VACUUM FULL tst;
+ SELECT count(*) FROM tst WHERE i = 16;
+  count 
+ -------
+     14
+ (1 row)
+ 
+ SELECT count(*) FROM tst WHERE t = '5';
+  count 
+ -------
+   1008
+ (1 row)
+ 
+ SELECT count(*) FROM tst WHERE i = 16 AND t = '5';
+  count 
+ -------
+      4
+ (1 row)
+ 
+ RESET enable_seqscan;
+ RESET enable_bitmapscan;
+ RESET enable_indexscan;
diff --git a/contrib/bloom/sql/bloom.sql b/contrib/bloom/sql/bloom.sql
new file mode 100644
index ...e5c7a86
*** a/contrib/bloom/sql/bloom.sql
--- b/contrib/bloom/sql/bloom.sql
***************
*** 0 ****
--- 1,46 ----
+ CREATE EXTENSION bloom;
+ 
+ CREATE TABLE tst (
+ 	i	int4,
+ 	t	text
+ );
+ 
+ \copy tst from 'data/data'
+ 
+ CREATE INDEX bloomidx ON tst USING bloom (i, t) WITH (col1 = 3);
+ 
+ SET enable_seqscan=on;
+ SET enable_bitmapscan=off;
+ SET enable_indexscan=off;
+ 
+ SELECT count(*) FROM tst WHERE i = 16;
+ SELECT count(*) FROM tst WHERE t = '5';
+ SELECT count(*) FROM tst WHERE i = 16 AND t = '5';
+ 
+ SET enable_seqscan=off;
+ SET enable_bitmapscan=on;
+ SET enable_indexscan=on;
+ 
+ EXPLAIN (COSTS OFF) SELECT count(*) FROM tst WHERE i = 16;
+ EXPLAIN (COSTS OFF) SELECT count(*) FROM tst WHERE t = '5';
+ EXPLAIN (COSTS OFF) SELECT count(*) FROM tst WHERE i = 16 AND t = '5';
+ 
+ SELECT count(*) FROM tst WHERE i = 16;
+ SELECT count(*) FROM tst WHERE t = '5';
+ SELECT count(*) FROM tst WHERE i = 16 AND t = '5';
+ 
+ VACUUM ANALYZE tst;
+ 
+ SELECT count(*) FROM tst WHERE i = 16;
+ SELECT count(*) FROM tst WHERE t = '5';
+ SELECT count(*) FROM tst WHERE i = 16 AND t = '5';
+ 
+ VACUUM FULL tst;
+ 
+ SELECT count(*) FROM tst WHERE i = 16;
+ SELECT count(*) FROM tst WHERE t = '5';
+ SELECT count(*) FROM tst WHERE i = 16 AND t = '5';
+ 
+ RESET enable_seqscan;
+ RESET enable_bitmapscan;
+ RESET enable_indexscan;
diff --git a/contrib/bloom/t/001_wal.pl b/contrib/bloom/t/001_wal.pl
new file mode 100644
index ...c0f8e64
*** a/contrib/bloom/t/001_wal.pl
--- b/contrib/bloom/t/001_wal.pl
***************
*** 0 ****
--- 1,75 ----
+ # Test generic xlog record work for bloom index replication.
+ use strict;
+ use warnings;
+ use PostgresNode;
+ use TestLib;
+ use Test::More tests => 31;
+ 
+ my $node_master;
+ my $node_standby;
+ 
+ # Run few queries on both master and stanbdy and check their results match.
+ sub test_index_replay
+ {
+ 	my ($test_name) = @_;
+ 
+ 	# Wait for standby to catch up
+ 	my $applname = $node_standby->name;
+ 	my $caughtup_query =
+ 		"SELECT pg_current_xlog_location() <= write_location FROM pg_stat_replication WHERE application_name = '$applname';";
+ 	$node_master->poll_query_until('postgres', $caughtup_query)
+ 	  or die "Timed out while waiting for standby 1 to catch up";
+ 
+ 	my $queries = qq(SET enable_seqscan=off;
+ SET enable_bitmapscan=on;
+ SET enable_indexscan=on;
+ SELECT * FROM tst WHERE i = 0;
+ SELECT * FROM tst WHERE i = 3;
+ SELECT * FROM tst WHERE t = 'b';
+ SELECT * FROM tst WHERE t = 'f';
+ SELECT * FROM tst WHERE i = 3 AND t = 'c';
+ SELECT * FROM tst WHERE i = 7 AND t = 'e';
+ );
+ 
+ 	# Run test queries and compare their result
+ 	my $master_result = $node_master->psql("postgres", $queries);
+ 	my $standby_result = $node_standby->psql("postgres", $queries);
+ 
+ 	is($master_result, $standby_result, "$test_name: query result matches");
+ }
+ 
+ # Initialize master node
+ $node_master = get_new_node('master');
+ $node_master->init(allows_streaming => 1);
+ $node_master->start;
+ my $backup_name = 'my_backup';
+ 
+ # Take backup
+ $node_master->backup($backup_name);
+ 
+ # Create streaming standby linking to master
+ $node_standby = get_new_node('standby');
+ $node_standby->init_from_backup($node_master, $backup_name,
+ 	has_streaming => 1);
+ $node_standby->start;
+ 
+ # Create some bloom index on master
+ $node_master->psql("postgres", "CREATE EXTENSION bloom;");
+ $node_master->psql("postgres", "CREATE TABLE tst (i int4, t text);");
+ $node_master->psql("postgres", "INSERT INTO tst SELECT i%10, substr(md5(i::text), 1, 1) FROM generate_series(1,100000) i;");
+ $node_master->psql("postgres", "CREATE INDEX bloomidx ON tst USING bloom (i, t) WITH (col1 = 3);");
+ 
+ # Test that queries give same result
+ test_index_replay('initial');
+ 
+ # Run 10 cycles of table modification. Run test queries after each modification.
+ for (my $i = 1; $i <= 10; $i++)
+ {
+ 	$node_master->psql("postgres", "DELETE FROM tst WHERE i = $i;");
+ 	test_index_replay("delete $i");
+ 	$node_master->psql("postgres", "VACUUM tst;");
+ 	test_index_replay("vacuum $i");
+ 	my ($start, $end) = (100001 + ($i - 1) * 10000, 100000 + $i * 10000);
+ 	$node_master->psql("postgres", "INSERT INTO tst SELECT i%10, substr(md5(i::text), 1, 1) FROM generate_series($start,$end) i;");
+ 	test_index_replay("insert $i");
+ }
diff --git a/doc/src/sgml/bloom.sgml b/doc/src/sgml/bloom.sgml
new file mode 100644
index ...c207e6d
*** a/doc/src/sgml/bloom.sgml
--- b/doc/src/sgml/bloom.sgml
***************
*** 0 ****
--- 1,218 ----
+ <!-- doc/src/sgml/bloom.sgml -->
+ 
+ <sect1 id="bloom" xreflabel="bloom">
+  <title>bloom</title>
+ 
+  <indexterm zone="bloom">
+   <primary>bloom</primary>
+  </indexterm>
+ 
+  <para>
+   <literal>bloom</> is a contrib which implements index access method.  It comes
+   as example of custom access methods and generic WAL records usage.  But it
+   is also useful itself.
+  </para>
+ 
+  <sect2>
+   <title>Introduction</title>
+ 
+   <para>
+    Implementation of
+    <ulink url="http://en.wikipedia.org/wiki/Bloom_filter">Bloom filter</ulink>
+    allows fast exclusion of non-candidate tuples.
+    Since signature is a lossy representation of all indexed attributes, 
+    search results should be rechecked using heap information. 
+    User can specify signature length (in uint16, default is 5) and the number of 
+    bits, which can be setted, per attribute (1 < colN < 2048).
+   </para>
+ 
+   <para>
+    This index is useful if table has many attributes and queries can include
+    their arbitary combinations.  Traditional <literal>btree</> index is faster
+    than bloom index, but it'd require too many indexes to support all possible 
+    queries, while one need only one bloom index.  Bloom index supports only 
+    equality comparison.  Since it's a signature file, not a tree, it always
+    should be readed fully, but sequentially, so index search performance is 
+    constant and doesn't depend on a query. 
+   </para>
+  </sect2>
+ 
+  <sect2>
+   <title>Parameters</title>
+ 
+   <para>
+    <literal>bloom</> indexes accept following parameters in <literal>WITH</>
+    clause.
+   </para>
+ 
+    <variablelist>
+    <varlistentry>
+     <term><literal>length</></term>
+     <listitem>
+      <para>
+       Length of signature in uint16 type values
+      </para>
+     </listitem>
+    </varlistentry>
+    </variablelist>
+    <variablelist>
+    <varlistentry>
+     <term><literal>col1 &mdash; col16</></term>
+     <listitem>
+      <para>
+       Number of bits for corresponding column
+      </para>
+     </listitem>
+    </varlistentry>
+    </variablelist>
+  </sect2>
+ 
+  <sect2>
+   <title>Examples</title>
+ 
+   <para>
+    Example of index definition is given below.
+   </para>
+ 
+ <programlisting>
+ CREATE INDEX bloomidx ON tbloom(i1,i2,i3) 
+        WITH (length=5, col1=2, col2=2, col3=4);
+ </programlisting>
+ 
+   <para>
+    Here, we create bloom index with signature length 80 bits and attributes
+    i1, i2  mapped to 2 bits, attribute i3 - to 4 bits.
+   </para>
+ 
+   <para>
+    Example of index definition and usage is given below.
+   </para>
+ 
+ <programlisting>
+ CREATE TABLE tbloom AS
+ SELECT
+     random()::int as i1,
+     random()::int as i2,
+     random()::int as i3,
+     random()::int as i4,
+     random()::int as i5,
+     random()::int as i6,
+     random()::int as i7,
+     random()::int as i8,
+     random()::int as i9,
+     random()::int as i10,
+     random()::int as i11,
+     random()::int as i12,
+     random()::int as i13
+ FROM
+     generate_series(1,1000);
+ CREATE INDEX bloomidx ON tbloom USING
+              bloom (i1, i2, i3, i4, i5, i6, i7, i8, i9, i10, i11, i12);
+ SELECT pg_relation_size('bloomidx');
+ CREATE index btree_idx ON tbloom(i1,i2,i3,i4,i5,i6,i7,i8,i9,i10,i11,i12);
+ SELECT pg_relation_size('btree_idx');
+ </programlisting>
+ 
+ <programlisting>
+ =# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 20 AND i10 = 15;
+                                                    QUERY PLAN
+ -----------------------------------------------------------------------------------------------------------------
+  Bitmap Heap Scan on tbloom  (cost=1.50..5.52 rows=1 width=52) (actual time=0.057..0.057 rows=0 loops=1)
+    Recheck Cond: ((i2 = 20) AND (i10 = 15))
+    ->  Bitmap Index Scan on bloomidx  (cost=0.00..1.50 rows=1 width=0) (actual time=0.041..0.041 rows=9 loops=1)
+          Index Cond: ((i2 = 20) AND (i10 = 15))
+  Total runtime: 0.081 ms
+ (5 rows)
+ </programlisting>
+ 
+   <para>
+    Seqscan is slow.
+   </para>
+ 
+ <programlisting>
+ =# SET enable_bitmapscan = off;
+ =# SET enable_indexscan = off;
+ =# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 20 AND i10 = 15;
+                                             QUERY PLAN
+ --------------------------------------------------------------------------------------------------
+  Seq Scan on tbloom  (cost=0.00..25.00 rows=1 width=52) (actual time=0.162..0.162 rows=0 loops=1)
+    Filter: ((i2 = 20) AND (i10 = 15))
+  Total runtime: 0.181 ms
+ (3 rows)
+ </programlisting>
+ 
+  <para>
+   Btree index will be not used for this query.
+  </para>
+ 
+ <programlisting>
+ =# DROP INDEX bloomidx;
+ =# CREATE INDEX btree_idx ON tbloom(i1, i2, i3, i4, i5, i6, i7, i8, i9, i10, i11, i12);
+ =# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 20 AND i10 = 15;
+                                             QUERY PLAN
+ --------------------------------------------------------------------------------------------------
+  Seq Scan on tbloom (cost=0.00..25.00 rows=1 width=52) (actual time=0.210..0.210 rows=0 loops=1)
+    Filter: ((i2 = 20) AND (i10 = 15))
+  Total runtime: 0.250 ms
+ (3 rows)
+ </programlisting>
+  </sect2>
+ 
+  <sect2>
+   <title>Opclass interface</title>
+ 
+   <para>
+    Bloom opclass interface is simple.  It requires 1 supporting function:
+    hash function for indexing datatype.  And it provides 1 search operator:
+    equality operator.  The example below shows <literal>opclass</> definition
+    for <literal>text</> datatype.
+   </para>
+ 
+ <programlisting>
+ CREATE OPERATOR CLASS text_ops
+ DEFAULT FOR TYPE text USING bloom AS
+     OPERATOR    1   =(text, text),
+     FUNCTION    1   hashtext(text);
+ </programlisting>
+  </sect2>
+ 
+  <sect2>
+   <title>Limitation</title>
+   <para>
+ 
+    <itemizedlist>
+     <listitem>
+      <para>
+       For now, only opclasses for <literal>int4</>, <literal>text</> comes
+       with contrib.  However, users may define more of them.
+      </para>
+     </listitem>
+ 
+     <listitem>
+      <para>
+       Only <literal>=</literal> operator is supported for search now.  But it's
+       possible to add support of arrays with contains and intersection
+       operations in future.
+      </para>
+     </listitem>
+    </itemizedlist>
+   </para>
+  </sect2>
+ 
+  <sect2>
+   <title>Authors</title>
+ 
+   <para>
+    Teodor Sigaev <email>teodor@postgrespro.ru</email>, Postgres Professional, Moscow, Russia
+   </para>
+ 
+   <para>
+    Alexander Korotkov <email>a.korotkov@postgrespro.ru</email>, Postgres Professional, Moscow, Russia
+   </para>
+ 
+   <para>
+    Oleg Bartunov <email>obartunov@postgrespro.ru</email>, Postgres Professional, Moscow, Russia
+   </para>
+  </sect2>
+ 
+ </sect1>
diff --git a/doc/src/sgml/contrib.sgml b/doc/src/sgml/contrib.sgml
new file mode 100644
index 1b3d2d9..c38b2f9
*** a/doc/src/sgml/contrib.sgml
--- b/doc/src/sgml/contrib.sgml
*************** CREATE EXTENSION <replaceable>module_nam
*** 105,110 ****
--- 105,111 ----
   &adminpack;
   &auth-delay;
   &auto-explain;
+  &bloom;
   &btree-gin;
   &btree-gist;
   &chkpass;
diff --git a/doc/src/sgml/filelist.sgml b/doc/src/sgml/filelist.sgml
new file mode 100644
index a12fee7..4a93ec2
*** a/doc/src/sgml/filelist.sgml
--- b/doc/src/sgml/filelist.sgml
***************
*** 106,111 ****
--- 106,112 ----
  <!ENTITY adminpack       SYSTEM "adminpack.sgml">
  <!ENTITY auth-delay      SYSTEM "auth-delay.sgml">
  <!ENTITY auto-explain    SYSTEM "auto-explain.sgml">
+ <!ENTITY bloom           SYSTEM "bloom.sgml">
  <!ENTITY btree-gin       SYSTEM "btree-gin.sgml">
  <!ENTITY btree-gist      SYSTEM "btree-gist.sgml">
  <!ENTITY chkpass         SYSTEM "chkpass.sgml">