package q3xx;

import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.Random;

public class N382_3 {
	InputStream is;
	PrintWriter out;
	String INPUT = "";
	
	void solve()
	{
		long S = ni();
		S = S * 12345 % 1000003;
		int n = (int)(S%120)+2;
		S = S * 12345 % 1000003;
		int p = (int)S;
		int m = (n>>>6)+1;
		long[][] g = new long[n][m];
		for(int i = 0;i < n;i++){
			for(int j = i+1;j < n;j++){
				S = S * 12345 % 1000003;
				if(S < p){
					g[i][j>>>6] |= 1L<<j;
					g[j][i>>>6] |= 1L<<i;
				}
			}
		}
		int[] res = MCS(g, TL);
		if(2 <= res.length+1 && res.length+1 <= n){
			out.println(res.length+1);
			for(int i = 0;i < res.length;i++){
				if(i > 0)out.print(" ");
				out.print(res[i]+1);
			}
			out.println();
		}else{
			out.println(-1);
		}
	}
	
	private static final int TL = 9000;
	private static final int STRICT_THRESHOLD = 200;
	private static final int LOCAL_SEARCH_CO = 5;
	private static final int INITIAL_SAMPLE_FIXED_THRESHOLD = 200;
	private static final int NUM_INITIAL_SAMPLE = 5;
	private static final int NUM_INITIAL_SAMPLE_BASE = 300000;
	
	public static boolean[] process(int[][] g, long S)
	{
		int n = g.length;
		int[] orig = new int[n]; for(int i = 0;i < n;i++)orig[i] = i;
		boolean[] is = new boolean[n];
		
		// remove duplicate edges
		for(int j = 0;j < g.length;j++){
			Arrays.sort(g[j]);
			g[j] = uniq(g[j]);
		}
		
		// remove degree 0 nodes
		{
			FilterResult fres = removeTrivialNodes(g, is, orig);
			for(int i = 0;i < g.length;i++){
				if(fres.map[i] != -1)orig[fres.map[i]] = orig[i];
			}
			g = fres.fg;
		}
		
		// remove trivial(degree 1) edges
		FilterResult fres = removeTrivialEdges(g, is, orig);
		if(fres != null){
			for(int i = 0;i < g.length;i++){
				if(fres.map[i] != -1)orig[fres.map[i]] = orig[i];
			}
			g = fres.fg;
		}
		
		SplitResult sr = split(g);
		int nbig = 0;
		for(int[] b : sr.buckets){
			if(b.length > STRICT_THRESHOLD)nbig++;
		}
		
		for(int i = 0;i < sr.buckets.length;i++){
			int[] b = sr.buckets[i];
			int[][] sg = sr.sg[i];
			if(b.length == 0)continue;
			if(b.length <= 2){
				is[orig[b[0]]] = true;
				continue;
			}
			if(b.length <= STRICT_THRESHOLD){
				long[][] fg = flip(sparseToPacked(sg));
				int[] mc = MCS(fg, TL);
				for(int x : mc)is[orig[b[x]]] = true;
			}
		}
		
		long G = System.currentTimeMillis();
		long tl = nbig == 0 ? 0 : (TL-(G-S))/nbig;
		for(int i = 0;i < sr.buckets.length;i++){
			int[] b = sr.buckets[i];
			int[][] sg = sr.sg[i];
			if(b.length > STRICT_THRESHOLD){
				
				// exact
				S = System.currentTimeMillis();
				long[][] fg = flip(sparseToPacked(sg));
				int[] mc = MCS(fg, tl);
				for(int x : mc)is[orig[b[x]]] = true;
			}
		}
		return is;
	}
	
	private static FilterResult removeTrivialNodes(int[][] g, boolean[] is, int[] orig)
	{
		int n = g.length;
		boolean[] filter = new boolean[n];
		for(int i = 0;i < n;i++){
			filter[i] = g[i].length > 0;
			if(g[i].length == 0){
				is[orig[i]] = true;
			}
		}
		return filter(filter, g);
	}
	
	private static FilterResult removeTrivialEdges(int[][] g, boolean[] is, int[] orig)
	{
		int n = g.length;
		int[] degs = new int[n];
		for(int i = 0;i < n;i++)degs[i] = g[i].length;
		boolean[] ved = new boolean[n];
		int[] q = new int[n];
		int p = 0;
		for(int i = 0;i < n;i++){
			if(degs[i] == 1){
				q[p++] = i;
				ved[i] = true;
			}
		}
		if(p == 0)return null;
		
		for(int r = 0;r < p;r++){
			int cur = q[r];
			if(degs[cur] < 1){
				// killed node
				degs[cur] = -1;
				for(int e : g[cur]){
					if(!ved[e] && --degs[e] == 1){
						ved[e] = true;
						q[p++] = e;
					}
				}
			}else{
				// stand node
				assert degs[cur] == 1;
				degs[cur] = -1;
				is[orig[cur]] = true;
				for(int e : g[cur]){
					degs[e] = -1; // even if e=stand node, kill.
					if(!ved[e]){
						ved[e] = true;
						q[p++] = e;
					}
				}
			}
		}
		boolean[] alive = new boolean[n];
		for(int i = 0;i < n;i++)alive[i] = degs[i] >= 0;
		return filter(alive, g);
	}
	
	public static FilterResult filter(boolean[] f, int[][] g)
	{
		int n = g.length;
		int[] map = new int[n];
		Arrays.fill(map, -1);
		int p = 0;
		for(int i = 0;i < n;i++){
			if(f[i])map[i] = p++;
		}
		int[][] h = new int[p][];
		int m = 0;
		for(int i = 0;i < n;i++)m = Math.max(m, g[i].length);
		int[] temp = new int[m+1];
		for(int i = 0;i < n;i++){
			if(f[i]){
				int q = 0;
				for(int e : g[i]){
					if(f[e])temp[q++] = map[e];
				}
				h[map[i]] = Arrays.copyOf(temp, q);
			}
		}
		FilterResult ret = new FilterResult();
		ret.map = map;
		ret.fg = h;
		return ret;
	}
	
	public static class FilterResult
	{
		int[][] fg;
		int[] map;
	}
	
	private static long[][] flip(long[][] g)
	{
		int n = g.length;
		for(int i = 0;i < n;i++){
			for(int j = 0;j < n>>>6;j++){
				g[i][j] = ~g[i][j];
			}
			g[i][n>>>6] ^= (1L<<n)-1;
		}
		return g;
	}
	
	private static long[][] sparseToPacked(int[][] g)
	{
		int n = g.length;
		int m = (n>>>6)+1;
		long[][] pg = new long[n][m];
		for(int i = 0;i < n;i++){
			for(int e : g[i]){
				pg[i][e>>>6] |= 1L<<e;
			}
		}
		return pg;
	}
	
	public static class DJSet {
		public int[] upper;

		public DJSet(int n) {
			upper = new int[n];
			Arrays.fill(upper, -1);
		}

		public int root(int x) {
			return upper[x] < 0 ? x : (upper[x] = root(upper[x]));
		}

		public boolean equiv(int x, int y) {
			return root(x) == root(y);
		}

		public boolean union(int x, int y) {
			x = root(x);
			y = root(y);
			if (x != y) {
				if (upper[y] < upper[x]) {
					int d = x;
					x = y;
					y = d;
				}
				upper[x] += upper[y];
				upper[y] = x;
			}
			return x == y;
		}

		public int count() {
			int ct = 0;
			for (int u : upper)
				if (u < 0)
					ct++;
			return ct;
		}
	}

	
	public static SplitResult split(int[][] g)
	{
		int n = g.length;
		DJSet ds = new DJSet(n);
		for(int i = 0;i < n;i++){
			for(int e : g[i]){
				ds.union(i, e);
			}
		}
		
		int cid = 0;
		int[] clus = new int[n];
		for(int i = 0;i < n;i++){
			if(ds.upper[i] < 0)clus[i] = cid++;
		}
		for(int i = 0;i < n;i++){
			clus[i] = clus[ds.root(i)];
		}
		int[][] buckets = makeBuckets(clus, cid);
		int[] iind = new int[n];
		for(int[] b : buckets){
			for(int i = 0;i < b.length;i++){
				iind[b[i]] = i;
			}
		}
		
		int[][][] sg = new int[cid+1][][];
		for(int i = 0;i < cid+1;i++){
			sg[i] = new int[buckets[i].length][];
			for(int j = 0;j < buckets[i].length;j++){
				int cur = buckets[i][j];
				sg[i][j] = new int[g[cur].length];
				for(int k = 0;k < g[cur].length;k++){
					sg[i][j][k] = iind[g[cur][k]];
				}
			}
		}
		SplitResult ret = new SplitResult();
		ret.sg = sg;
		ret.buckets = buckets;
		return ret;
	}
	
	public static class SplitResult
	{
		public int[][] buckets;
		public int[][][] sg;
	}
	
	public static int[][] makeBuckets(int[] a, int sup)
	{
		int n = a.length;
		int[][] bucket = new int[sup+1][];
		int[] bp = new int[sup+1];
		for(int i = 0;i < n;i++)bp[a[i]]++;
		for(int i = 0;i <= sup;i++)bucket[i] = new int[bp[i]];
		for(int i = n-1;i >= 0;i--)bucket[a[i]][--bp[a[i]]] = i;
		return bucket;
	}
	
	public static int[] uniq(int[] a)
	{
		int n = a.length;
		int p = 0;
		for(int i = 0;i < n;i++) {
			if(i == 0 || a[i] != a[i-1])a[p++] = a[i];
		}
		return p == n ? a : Arrays.copyOf(a, p);
	}
	
	static int size(boolean[] a)
	{
		int ret = 0;
		for(boolean v : a)if(v)ret++;
		return ret;
	}
	
	public static class XorShift extends Random {
		private static final long serialVersionUID = 6806629989739663134L;
		private long x=123456789, y=362436069, z=521288629, w=88675123;
		public XorShift() {super(); x = System.nanoTime();}
		public XorShift(long seed) {super(seed); x = seed;}
		public synchronized void setSeed(long seed) {super.setSeed(seed); x = seed;}
		protected int next(int bits){
			long t=(x^x<<11)&(1L<<32)-1; x=y; y=z; z=w; w=(w^w>>>19^t^t>>>8)&(1L<<32)-1;
			return (int)w>>>32-bits;
		}
	}
	
	public static int[] MCS(long[][] g, long timeout)
	{
		long S = System.currentTimeMillis();
		int n = g.length;
		int m = (n>>>6)+1;
		if(n == 0)return new int[0];
		long[] Qmax = new long[m];
		
		int[] no = new int[n];
		int[] V = new int[n];
		
		extendedInitialSortNumber(V, no, Qmax, g);
		long[] nQmax = new long[m];
		for(int i = 0;i < n;i++)if(Qmax[V[i]>>>6]<<~V[i]<0)nQmax[i>>>6] |= 1L<<i;
		int[] nno = new int[n];
		for(int i = 0;i < n;i++)nno[i] = no[V[i]];
		long[][] ng = new long[n][m];
		for(int i = 0;i < n;i++){
			for(int j = i+1;j < n;j++){
				if(g[V[i]][V[j]>>>6]<<~V[j]<0){
					ng[i][j>>>6] |= 1L<<j;
					ng[j][i>>>6] |= 1L<<i;
				}
			}
		}
		
		long[] nv = new long[m];
		fill(nv, n);
		
		int[] nr = new int[n];
		for(int i = 0;i < n;i++)nr[i] = i;
		
		nos = new int[n][n];
		nos[0] = nno;
		C = new long[n+2][m];
//		{
//			int[] rec = reconstruct(nQmax, V);
//			check(rec, g);
//		}
		try {
			expandS(nv, nr, 0, new long[m], nQmax, ng, S+timeout);
		} catch (Exception e) {
		}
		int[] rec = reconstruct(nQmax, V);
		return rec;
	}
	
	private static int[] reconstruct(long[] Qmax, int[] V)
	{
		int m = size(Qmax);
		int[] ret = new int[m];
		int p = 0;
		for(int i = 0;i < Qmax.length;i++){
			for(long j = Qmax[i];j != 0;j&=j-1){
				int id = Long.numberOfTrailingZeros(j)|i<<6;
				ret[p++] = V[id];
			}
		}
		assert p == m;
		Arrays.sort(ret);
		return ret;
	}
	
	private static void fill(long[] a, int n)
	{
		for(int i = 0;i < a.length && i < n>>>6;i++){
			a[i] = -1L;
		}
		if((n&63) != 0)a[n>>>6] = (1L<<n)-1;
	}
	
	private static int[][] nos;
//	private static int[] add = new int[100000];
//	private static int ap;
	
	private static void expandS(long[] Va, int[] R, int depno, long[] Q, long[] Qmax, long[][] g, long expired)
	{
		int n = g.length;
		int m = (n>>>6)+1;
		
		if(System.currentTimeMillis() > expired)throw new RuntimeException();
		int[] no = nos[depno];
		for(int j = R.length-1;j >= 0;j--){
			int p = R[j];
			assert no[p] >= 1;
			if(depno == 0 || size(Q) + no[p] > size(Qmax)){
				Q[p>>>6] |= 1L<<p;
				Va[p>>>6] ^= 1L<<p;
				long[] Vp = new long[Va.length];
				for(int k = 0;k < m;k++){
					Vp[k] = Va[k]&g[p][k];
				}
				if(!empty(Vp)){
//					ap = 0;
//					int res = renumberSortLight(Vp, g);
//
//					int[] ladds = Arrays.copyOf(add, ap);
//					for(int ladd : ladds){
//						assert Q[ladd>>>6]<<~ladd>=0;
//						assert Vp[ladd>>>6]<<~ladd<0;
//						Q[ladd>>>6] ^= 1L<<ladd;
//						Vp[ladd>>>6] ^= 1L<<ladd;
//					}
//					if(size(Q) > size(Qmax)){
//						for(int kk = 0;kk < Qmax.length;kk++)Qmax[kk] = Q[kk];
//					}
					
					int[] newR = new int[size(Vp)];
					int[] newNo = nos[depno+1];
					int k = renumberSort(Vp, newR, newNo, g, size(Qmax)-size(Q));
					newR = Arrays.copyOfRange(newR, k, newR.length);
					expandS(Vp, newR, depno+1, Q, Qmax, g, expired);
//					for(int ladd : ladds){
//						assert Q[ladd>>>6]<<~ladd<0;
//						Q[ladd>>>6] ^= 1L<<ladd;
//						Vp[ladd>>>6] ^= 1L<<ladd;
//					}
				}else if(size(Q) > size(Qmax)){
					for(int k = 0;k < Qmax.length;k++)Qmax[k] = Q[k];
				}
				Q[p>>>6] ^= 1L<<p;
			}else{
				if(depno > 0)break; // If we are not at the first level of recursion return from recursion because the candidates are ordered by colours and all the remaining candidates have a smaller colour number.
			}
		}
	}
	
	private static void ReNUMBER(int p, int[] no, int nop, int noth, long[][] c, long[][] g)
	{
		int n = g.length;
		int m = (n>>>6)+1;
		for(int k1 = 1;k1 <= noth-1;k1++){
			int inter = 0;
			int q = -1;
			for(int i = 0;i < m;i++){
				long inte = g[p][i]&c[k1][i];
				int icb = Long.bitCount(inte);
				inter += icb;
				if(inter >= 2)break;
				if(icb == 1){
					q = Long.numberOfTrailingZeros(inte)|i<<6;
				}
			}
			if(inter == 1){
				assert q != -1;
				inner:
				for(int k2 = k1 + 1;k2 <= noth;k2++){
					for(int i = 0;i < m;i++){
						if((g[q][i]&c[k2][i]) != 0)continue inner;
					}
					no[q] = k2;
					no[p] = k1;
					assert p != q;
					assert c[nop][p>>>6]<<~p<0;
					assert c[k1][p>>>6]<<~p>=0;
					assert c[k1][q>>>6]<<~q<0;
					assert c[k2][q>>>6]<<~q>=0;
					c[nop][p>>>6] ^= 1L<<p;
					c[k1][p>>>6] ^= 1L<<p;
					c[k1][q>>>6] ^= 1L<<q;
					c[k2][q>>>6] ^= 1L<<q;
					return;
				}
			}
		}
	}
	
	private static long[][] C;
	
	// in: Va, noth
	// out: R,no
	private static int renumberSort(long[] Va, int[] R, int[] no, long[][] g, int noth)
	{
//		Arrays.fill(R, -1);
//		Arrays.fill(no, -1);
		int n = g.length;
		int m = (n>>>6)+1;
		int maxno = 0;
		for(int z = 0;z < m;z++){
			for(long y = Va[z];y != 0;y&=y-1){
				int p = Long.numberOfTrailingZeros(y)|z<<6;
				// Conventional greedy approximate coloring
				int k = 1;
				
				inner:
				while(k <= maxno){
					for(int i = 0;i < m;i++){
						if((g[p][i]&C[k][i]) != 0){
							k++;
							continue inner;
						}
					}
					break;
				}
				if(k > maxno){
					maxno = k;
					Arrays.fill(C[k], 0L);
				}
				no[p] = k;
				C[k][p>>>6] |= 1L<<p;
				
				// Re-NUMBER
				if(k > noth && k == maxno){
					ReNUMBER(p, no, k, noth, C, g);
					if(empty(C[maxno])){
						maxno--;
					}
				}
			}
		}
		
		int i = size(Va);
		if(noth < 0)noth = 0;
		int k;
		for(k = maxno;k >= noth+1;k--){
			for(int j = m-1;j >= 0;j--){
				for(long y = C[k][j];y != 0;y^=Long.highestOneBit(y)){
					int x = j<<6|63-Long.numberOfLeadingZeros(y);
					i--;
					R[i] = x;
					no[R[i]] = k;
				}
			}
		}
		if(i != 0){
			k--;
			for(int j = m-1;j >= 0;j--){
				if(C[k][j] != 0){
					int x = j<<6|63-Long.numberOfLeadingZeros(C[k][j]);
					i--;
					R[i] = x;
					no[R[i]] = noth;
					break;
				}
			}
		}
		return i;
	}
	
	public static int size(long[] a)
	{
		int ret = 0;
		for(long v : a)ret += Long.bitCount(v);
		return ret;
	}
	
	public static boolean empty(long[] a)
	{
		for(long v : a)if(v != 0)return false;
		return true;
	}
	
	public static int min(long[] a)
	{
		for(int i = 0;i < a.length;i++){
			if(a[i] != 0L)return Long.numberOfTrailingZeros(a[i])|i<<6;
		}
		return -1;
	}
	
	private static void extendedInitialSortNumber(int[] V, int[] no, long[] Qmax, long[][] g)
	{
		int n = g.length;
		int[] degs = new int[n];
		int maxdeg = 0;
		for(int i = 0;i < n;i++){
			degs[i] = size(g[i]);
			maxdeg = Math.max(maxdeg, degs[i]);
		}
		
		// SORT
		long[] R = new long[(n>>>6)+1];
		fill(R, n);
		int vp = n;
		long[] Rmin = rmin(R, degs);
		while(size(Rmin) != size(R)){
			int p = min(Rmin);
			if(size(Rmin) >= 2){
				int minv = Integer.MAX_VALUE;
				for(int i = 0;i < Rmin.length;i++){
					for(long j = Rmin[i];j != 0;j&=j-1){
						int id = Long.numberOfTrailingZeros(j)|i<<6;
						int lv = exdeg(id, degs, g);
						if(lv < minv){
							minv = lv;
							p = id;
						}
					}
				}
			}
			V[--vp] = p;
			R[p>>>6] ^= 1L<<p;
			
			for(int i = 0;i < R.length;i++){
				for(long j = R[i]&g[p][i];j != 0;j&=j-1){
					int id = Long.numberOfTrailingZeros(j)|i<<6;
					degs[id]--;
				}
			}
			Rmin = rmin(R, degs);
		}
		
		// Regular subgraph
		numberSort(Rmin, no, g);
		int ii = 0;
		for(int i = 0;i < Rmin.length;i++){
			for(long j = Rmin[i];j != 0;j&=j-1){
				int id = Long.numberOfTrailingZeros(j)|i<<6;
				V[ii++] = id;
			}
		}
		
		// NUMBER
		NUMBER: {
			int m = 0;
			for(int i = 0;i < Rmin.length;i++){
				for(long j = Rmin[i];j != 0;j&=j-1){
					int id = Long.numberOfTrailingZeros(j)|i<<6;
					m = Math.max(m, no[id]);
				}
			}
			int mmax = size(Rmin) + maxdeg - m;
			m++;
			for(int i = size(Rmin);i < mmax;i++){
				if(i >= n)break NUMBER;
				no[V[i]] = m++;
			}
			for(int i = mmax;i < n;i++){
				no[V[i]] = maxdeg + 1;
			}
		}
		
		// START
		if(n >= 4){
			Random gen = new XorShift();
			long[][] fg = new long[n][];
			for(int i = 0;i < n;i++){
				fg[i] = Arrays.copyOf(g[i], g[i].length);
			}
			fg = flip(fg);
			long[] is = new long[(n>>>6)+1];
			int lim = n <= INITIAL_SAMPLE_FIXED_THRESHOLD ? NUM_INITIAL_SAMPLE : NUM_INITIAL_SAMPLE_BASE/n/((n>>>6)+1);
			for(int rep = 0;rep < lim;rep++){
				long[] can = initialSample(fg, gen);
				if(size(can) > size(is)){
					is = can;
				}
			}
			for(int i = 0;i < is.length;i++){
				Qmax[i] = is[i];
			}
		}
	}
	
	private static long[] initialSample(long[][] g, Random gen)
	{
		int n = g.length;
		long[] a = new long[n];
		for(int i = 0;i < n;i++){
			int deg = size(g[i]);
			a[i] = (long)gen.nextInt((int)Math.min(2000000000L, deg*deg*100L)+1)<<32|i;
		}
		Arrays.sort(a);
		int m = (n>>>6)+1;
		long[] is = new long[m];
		long[] temp = new long[m];
		outer:
		for(int i = 0;i < n;i++){
			int cur = (int)a[i];
			for(int j = 0;j < m;j++){
				if((g[cur][j]&is[j]) != 0)continue outer;
			}
			is[cur>>>6] |= 1L<<cur;
		}
		
		// local search
		int[] iss = new int[n];
		int ip = 0;
		int[] covered = new int[n];
		long[] c1 = new long[m];
		long[] c0 = new long[m];
		for(int i = 0;i < n;i++){
			if(is[i>>>6]<<~i<0){
				iss[ip++] = i;
				add(i, 1, covered, g, c0, c1);
			}
		}
		if(ip == 0)return is;
		
		for(int i = 0;i < n;i++){
			if(covered[i] == 0){
				c0[i>>>6] |= 1L<<i;
			}else if(covered[i] == 1){
				c1[i>>>6] |= 1L<<i;
			}
		}
		for(int rep = 0;rep < LOCAL_SEARCH_CO*n;rep++){
			int ind = gen.nextInt(ip);
			int id = iss[ind];
			
			for(int j = 0;j < m;j++){ // id's neighbor and covered by one.
				temp[j] = c1[j]&g[id][j]&~is[j];
			}
			int szt = size(temp);
			if(szt == 0)continue;
			if(szt >= 2 && gen.nextInt(3) == 0){
				int u = select(temp, gen.nextInt(szt));
				assert temp[u>>>6]<<~u<0;
				temp[u>>>6] ^= 1L<<u;
				for(int j = 0;j < m;j++){
					temp[j] &= ~g[u][j];
				}
				szt = size(temp);
				if(szt == 0)continue;
				int v = select(temp, gen.nextInt(size(temp)));
				assert is[id>>>6]<<~id<0;
				assert is[u>>>6]<<~u>=0;
				assert is[v>>>6]<<~v>=0;
				is[id>>>6] ^= 1L<<id;
				is[u>>>6] ^= 1L<<u;
				is[v>>>6] ^= 1L<<v;
				iss[ind] = u;
				iss[ip++] = v;
				add(id, -1, covered, g, c0, c1);
				add(u, 1, covered, g, c0, c1);
				add(v, 1, covered, g, c0, c1);
				continue;
			}
			int u = select(temp, gen.nextInt(szt));
			assert is[u>>>6]<<~u>=0;
			is[id>>>6] ^= 1L<<id;
			is[u>>>6] ^= 1L<<u;
			add(id, -1, covered, g, c0, c1);
			add(u, 1, covered, g, c0, c1);
			iss[ind] = u;
		}
//		if(n >= 150)tr(O, "=>", size(is));
		return is;
	}
	
	static int select(long[] a, int K)
	{
		int offset = 0;
		for(long v : a){
			int bc = Long.bitCount(v);
			if(K < bc){
				for(int i = 0;i < K;i++)v &= v-1;
				return Long.numberOfTrailingZeros(v) + offset;
			}else{
				K -= bc;
				offset += 64;
			}
		}
		return -1;
	}
	
	private static void add(int i, int plus, int[] covered, long[][] g, long[] c0, long[] c1)
	{
		int m = (g.length>>>6)+1;
		if(covered[i] == 1)c1[i>>>6] ^= 1L<<i;
		if(covered[i] == 0)c0[i>>>6] ^= 1L<<i;
		covered[i] += plus;
		if(covered[i] == 1)c1[i>>>6] ^= 1L<<i;
		if(covered[i] == 0)c0[i>>>6] ^= 1L<<i;
		for(int j = 0;j < m;j++){
			for(long x = g[i][j];x != 0;x&=x-1){
				int id = Long.numberOfTrailingZeros(x)|j<<6;
				if(covered[id] == 1)c1[id>>>6] ^= 1L<<id;
				if(covered[id] == 0)c0[id>>>6] ^= 1L<<id;
				covered[id] += plus;
				if(covered[id] == 1)c1[id>>>6] ^= 1L<<id;
				if(covered[id] == 0)c0[id>>>6] ^= 1L<<id;
			}
		}
	}
	
	private static int exdeg(int q, int[] degs, long[][] g)
	{
		int ret = 0;
		for(int i = 0;i < g[q].length;i++){
			for(long j = g[q][i];j != 0;j&=j-1){
				int id = Long.numberOfTrailingZeros(j)|i<<6;
				ret += degs[id];
			}
		}
		return ret;
	}
	
	private static long[] rmin(long[] R, int[] degs)
	{
		int mindeg = 9999;
		long[] Rmin = new long[R.length];
		for(int i = 0;i < R.length;i++){
			for(long j = R[i];j != 0;j&=j-1){
				int v = Long.numberOfTrailingZeros(j)|i<<6;
				if(degs[v] < mindeg){
					mindeg = degs[v];
					Rmin[v>>>6] |= 1L<<v;
				}else if(degs[v] == mindeg){
					Arrays.fill(Rmin, 0L);
					Rmin[v>>>6] |= 1L<<v;
				}
			}
		}
		return Rmin;
	}
	
	private static void numberSort(long[] R, int[] no, long[][] g)
	{
		int n = g.length;
		int maxno = 0;
		int m = (n>>>6)+1;
		long[][] c = new long[size(R)+1][m];
		for(int z = 0;z < R.length;z++){
			for(long j = R[z];j != 0;j &= j-1){
				int p = Long.numberOfTrailingZeros(j)|z<<6;
				int k = 1;
				
				inner:
				while(true){
					for(int i = 0;i < m;i++){
						if((g[p][i]&c[k][i]) != 0){
							k++;
							continue inner;
						}
					}
					break;
				}
				if(k > maxno){
					maxno = k;
				}
				no[p] = k;
				c[k][p>>>6] |= 1L<<p;
			}
		}
		// sort
		int i = 0;
		for(int k = 1;k <= maxno;k++){
			for(int u = 0;u < m;u++){
				for(long j = c[k][u];j != 0;j &= j-1){
					int p = Long.numberOfTrailingZeros(j)|u<<6;
					i++;
					R[p>>>6] |= 1L<<p;
				}
			}
		}
		assert i == size(R);
	}
		
	void run() throws Exception
	{
		is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new PrintWriter(System.out);
		
		long s = System.currentTimeMillis();
		solve();
		out.flush();
		if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
	}
	
	public static void main(String[] args) throws Exception { new N382_3().run(); }
	
	private byte[] inbuf = new byte[1024];
	private int lenbuf = 0, ptrbuf = 0;
	
	private int readByte()
	{
		if(lenbuf == -1)throw new InputMismatchException();
		if(ptrbuf >= lenbuf){
			ptrbuf = 0;
			try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
			if(lenbuf <= 0)return -1;
		}
		return inbuf[ptrbuf++];
	}
	
	private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
	private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
	
	private double nd() { return Double.parseDouble(ns()); }
	private char nc() { return (char)skip(); }
	
	private String ns()
	{
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	
	private char[] ns(int n)
	{
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while(p < n && !(isSpaceChar(b))){
			buf[p++] = (char)b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}
	
	private char[][] nm(int n, int m)
	{
		char[][] map = new char[n][];
		for(int i = 0;i < n;i++)map[i] = ns(m);
		return map;
	}
	
	private int[] na(int n)
	{
		int[] a = new int[n];
		for(int i = 0;i < n;i++)a[i] = ni();
		return a;
	}
	
	private int ni()
	{
		int num = 0, b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}
		
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private long nl()
	{
		long num = 0;
		int b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}
		
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}