Problem: Mahmoud and Ehab are in the fourth stage now.

Dr. Evil has a hidden binary string of length n. He guarantees that there is at least one '0' symbol and at least one '1' symbol in it. Now he wants Mahmoud and Ehab to find a position of any '0' symbol and any '1' symbol. In order to do this, Mahmoud and Ehab can ask Dr. Evil up to 15 questions. They tell Dr. Evil some binary string of length n, and Dr. Evil tells the Hamming distance between these two strings. Hamming distance between 2 binary strings of the same length is the number of positions in which they have different symbols. You can find the definition of Hamming distance in the notes section below.

Help Mahmoud and Ehab find these two positions.

You will get Wrong Answer verdict if 

  * Your queries doesn't satisfy interaction protocol described below. 
  * You ask strictly more than 15 questions and your program terminated after exceeding queries limit. Please note, that you can do up to 15 ask queries and one answer query. 
  * Your final answer is not correct. 

You will get Idleness Limit Exceeded if you don't print anything or if you forget to flush the output, including for the final answer (more info about flushing output below).

If you exceed the maximum number of queries, You should terminate with 0, In this case you'll get Wrong Answer, If you don't terminate you may receive any verdict because you'll be reading from a closed stream .

Input

The first line of input will contain a single integer n (2 ≤ n ≤ 1000) — the length of the hidden binary string.

Output

To print the final answer, print "! pos0 pos1" (without quotes), where pos0 and pos1 are positions of some '0' and some '1' in the string (the string is 1-indexed). Don't forget to flush the output after printing the answer!

Interaction

To ask a question use the format "? s" (without quotes), where s is a query string. Don't forget to flush the output after printing a query!

After each query you can read a single integer from standard input — the Hamming distance between the hidden string and the query string.

To flush the output you can use:- 

  * fflush(stdout) in C++; 
  * System.out.flush() in Java; 
  * stdout.flush() in Python; 
  * flush(output) in Pascal; 
  * See the documentation for other languages . 



Hacking.

To hack someone just print one binary string with length up to 1000, containing at least one '0' and at least one '1'.

Example

Input

3
2
1
3
2
1
0

Output

? 000
? 001
? 010
? 011
? 100
? 101
! 2 1

Note

Hamming distance definition: <https://en.wikipedia.org/wiki/Hamming_distance>

In the first test case the hidden binary string is 101, The first query is 000, so the Hamming distance is 2. In the second query the hidden string is still 101 and query is 001, so the Hamming distance is 1.

After some queries you find that symbol at position 2 is '0' and symbol at position 1 is '1', so you print "! 2 1".

Solution (in JAVA):

Solution:
import java.util.*;
import java.io.*;
import java.lang.Math.*;

public class MainA
{

	static int mod = (int) 1e9 + 7;

	public static void main(String[] args) throws java.lang.Exception
	{
		InputReader in = new InputReader(System.in);
		
		int n=in.nextInt();
		String st="";
		for(int i=0;i<n;i++)
		{
			st+="0";
		}
		System.out.println("? "+st);
		System.out.flush();
		int count1=in.nextInt();
		
		StringBuffer str=new StringBuffer(st);
		
		int mid=(n-1)/2;
		str.replace(mid,mid+1,"1");
		System.out.println("? "+str);
		System.out.flush();
		int ans=in.nextInt();
		int pos1=0,pos0=0;
		boolean flag0=false,flag1=false;
		if(ans==count1-1)
		{
			pos1=mid;
			flag1=true;
			if(n==2)
			{
				if(pos1==0)pos0=1;
				else pos0=0;
				System.out.println("! "+(pos0+1)+" "+(pos1+1));
				return;
			}
		}
		else
		{
			pos0=mid;
			flag0=true;
			if(n==2)
			{
				if(pos0==0)pos1=1;
				else pos1=0;
				System.out.println("! "+(pos0+1)+" "+(pos1+1));
				return;
			}
		}
		
		if(flag0)
		{
			int count=0;
			int left=0,right=n-1;
			while(true)
			{
				st="";
				for(int i=0;i<n;i++)
				{
					st+="0";
				}
				str=new StringBuffer(st);
				mid=(left+right)/2;
				for(int i=left;i<=mid;i++)
				{
					str.replace(i,i+1,"1");
				}
				if(count==0)
				{
					str.replace(mid, mid+1, "0");
				}
				System.out.println("? "+str);
				System.out.flush();
				ans=in.nextInt();
				if(count==0)mid--;
				if(ans==count1+mid-left+1)
				{
					if(count==0)
					mid++;
					left=mid+1;
					//System.out.println("left "+left);
				}
				else
				{
					right=mid;
					
					//System.out.println("right "+right);
				}
				
				if(left==right)
				{
					pos1=left;
					break;
				}
				count++;
			}
			
			System.out.println("! "+(pos0+1)+" "+(pos1+1));
			System.out.flush();
		}
		else
		{
			int count=0;
			int left=0,right=n-1;
			while(true)
			{
				st="";
				for(int i=0;i<n;i++)
				{
					st+="1";
				}
				str=new StringBuffer(st);
				mid=(left+right)/2;
				for(int i=left;i<=mid;i++)
				{
					str.replace(i,i+1,"0");
				}
				if(count==0)
				{
					str.replace(mid, mid+1, "1");
				}
				System.out.println("? "+str);
				System.out.flush();
				ans=in.nextInt();
				if(count==0)mid--;
				if(ans==(n-count1)+mid-left+1)
				{
					if(count==0)mid++;
					left=mid+1;
					//System.out.println("left "+left);
					System.out.flush();
				}
				else
				{
					right=mid;
					
					//System.out.println("right "+right);
					System.out.flush();
				}
				
				if(left==right)
				{
					pos0=left;
					break;
				}
				count++;
			}
			
			System.out.println("! "+(pos0+1)+" "+(pos1+1));
			System.out.flush();
		}
		
	}

	
	static class Pairs implements Comparable<Pairs>
	{
		int x;
		int y;
		
		
		Pairs(int a, int b)
		{
			x = a;
			y = b;
			
		}

		@Override
		public int compareTo(Pairs o)
		{
			// TODO Auto-generated method stub
			return Integer.compare(x,o.x);
		}

	}

	public static void debug(Object... o) 
	{
		System.out.println(Arrays.deepToString(o));
	}

	public static boolean isPal(String s) 
	{
		for (int i = 0, j = s.length() - 1; i <= j; i++, j--)
		{
			if (s.charAt(i) != s.charAt(j))
				return false;
		}
		return true;
	}

	public static String rev(String s)
	{
		StringBuilder sb = new StringBuilder(s);
		sb.reverse();
		return sb.toString();
	}

	public static long gcd(long x, long y)
	{
		if (y == 0)
			return x;
		if (x % y == 0)
			return y;
		else
			return gcd(y, x % y);
	}

	public static int gcd(int x, int y)
	{
		if(y==0)
			return x;
		if (x % y == 0)
			return y;
		else
			return gcd(y, x % y);
	}

	public static long gcdExtended(long a, long b, long[] x) 
	{

		if (a == 0) 
		{
			x[0] = 0;
			x[1] = 1;
			return b;
		}
		long[] y = new long[2];
		long gcd = gcdExtended(b % a, a, y);

		x[0] = y[1] - (b / a) * y[0];
		x[1] = y[0];

		return gcd;
	}

	
	

	public static long max(long a, long b) 
	{
		if (a > b)
			return a;
		else
			return b;
	}

	public static long min(long a, long b)
	{
		if (a > b)
			return b;
		else
			return a;
	}

	public static long[][] mul(long a[][], long b[][])
	{
		long c[][] = new long[2][2];
		c[0][0] = a[0][0] * b[0][0] + a[0][1] * b[1][0];
		c[0][1] = a[0][0] * b[0][1] + a[0][1] * b[1][1];
		c[1][0] = a[1][0] * b[0][0] + a[1][1] * b[1][0];
		c[1][1] = a[1][0] * b[0][1] + a[1][1] * b[1][1];

		return c;
	}

	public static long[][] pow(long n[][], long p, long m)
	{
		long result[][] = new long[2][2];
		result[0][0] = 1;
		result[0][1] = 0;
		result[1][0] = 0;
		result[1][1] = 1;

		if (p == 0)
			return result;
		if (p == 1)
			return n;
		while (p != 0)
		{
			if (p % 2 == 1)
				result = mul(result, n);
			//System.out.println(result[0][0]);
			for (int i = 0; i < 2; i++)
			{
				for (int j = 0; j < 2; j++)
				{
					if (result[i][j] >= m)
						result[i][j] %= m;
				}
			}

			p >>= 1;
			n = mul(n, n);
			// System.out.println(1+" "+n[0][0]+" "+n[0][1]+" "+n[1][0]+" "+n[1][1]);
			for (int i = 0; i < 2; i++) 
			{
				for (int j = 0; j < 2; j++)
				{
					if (n[i][j] >= m)
						n[i][j] %= m;
				}
			}
		}
		return result;
	}
	public static long pow(long n,long p, long m)
	{
		long result=1;
		if(p==0)return 1;
		if(p==1)return n%m;
		while(p!=0)
		{
			if(p%2==1)result=(result*n)%m;
			p >>=1;
			n=(n*n)%m;
		}
		return result;
	}
	public static long pow(long n, long p) 
	{
		long result = 1;
		if (p == 0)
			return 1;
		if (p == 1)
			return n;
		while (p != 0)
		{
			if (p % 2 == 1)
				result *= n;
			p >>= 1;
			n *= n;
		}
		return result;
	}

	static class InputReader {

		private final InputStream stream;
		private final byte[] buf = new byte[8192];
		private int curChar, snumChars;
		private SpaceCharFilter filter;

		public InputReader(InputStream stream)
		{
			this.stream = stream;
		}

		public int snext()
		{
			if (snumChars == -1)
				throw new InputMismatchException();
			if (curChar >= snumChars)
			{
				curChar = 0;
				try 
				{
					snumChars = stream.read(buf);
				}
				catch (IOException e)
				{
					throw new InputMismatchException();
				}
				if (snumChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		public int nextInt()
		{
			int c = snext();
			while (isSpaceChar(c))
			{
				c = snext();
			}
			int sgn = 1;
			if (c == '-')
			{
				sgn = -1;
				c = snext();
			}
			int res = 0;
			do
			{
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = snext();
			}
			while (!isSpaceChar(c));
			return res * sgn;
		}

		public long nextLong()
		{
			int c = snext();
			while (isSpaceChar(c))
			{
				c = snext();
			}
			int sgn = 1;
			if (c == '-') 
			{
				sgn = -1;
				c = snext();
			}
			long res = 0;
			do 
			{
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = snext();
			}
			while (!isSpaceChar(c));
			return res * sgn;
		}

		public int[] nextIntArray(int n)
		{
			int a[] = new int[n];
			for (int i = 0; i < n; i++)
			{
				a[i] = nextInt();
			}
			return a;
		}

		public long[] nextLongArray(int n)
		{
			long a[] = new long[n];
			for (int i = 0; i < n; i++) 
			{
				a[i] = nextInt();
			}
			return a;
		}

		public String readString()
		{
			int c = snext();
			while (isSpaceChar(c))
			{
				c = snext();
			}
			StringBuilder res = new StringBuilder();
			do 
			{
				res.appendCodePoint(c);
				c = snext();
			} 
			while (!isSpaceChar(c));
			return res.toString();
		}

		public String nextLine()
		{
			int c = snext();
			while (isSpaceChar(c))
				c = snext();
			StringBuilder res = new StringBuilder();
			do
			{
				res.appendCodePoint(c);
				c = snext();
			}
			while (!isEndOfLine(c));
			return res.toString();
		}

		public boolean isSpaceChar(int c) 
		{
			if (filter != null)
				return filter.isSpaceChar(c);
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		private boolean isEndOfLine(int c)
		{
			return c == '\n' || c == '\r' || c == -1;
		}

		public interface SpaceCharFilter 
		{
			public boolean isSpaceChar(int ch);
		}
	}
}