/* ACM ICPC Asia Regional Contest, Hakodate 2001 Problem G: Nim by Naoyuki Tamura (tamura@kobe-u.ac.jp) */ import java.io.*; import java.util.*; public class G { static boolean dbg = false; static String infile = "nim.txt"; static DataInputStream in = new DataInputStream(System.in); static int N; static int[] max1; static int[] max2; static int stones; static int[][] stat1; static int[][] stat2; static final int UNKNOWN = 0; static final int WON = 1; static final int LOOSE = 2; static void debug(String msg) { if (dbg) System.err.print(msg); } static boolean read() throws Exception { String line = null; debug("# Enter\n"); line = in.readLine(); StringTokenizer st = new StringTokenizer(line); N = Integer.parseInt(st.nextToken()); if (N == 0) return false; stones = Integer.parseInt(st.nextToken()); max1 = new int[N]; max2 = new int[N]; for (int i = 0; i < N; i++) { max1[i] = Integer.parseInt(st.nextToken()); max2[i] = Integer.parseInt(st.nextToken()); } return true; } static boolean win1(int stones, int i) { int remain; if (stat1[i][stones] != UNKNOWN) return stat1[i][stones] == WON; for (int s = 1; s <= max1[i]; s++) { remain = stones - s; if (remain <= 0) break; if (! win2(remain, i)) { stat1[i][stones] = WON; return true; } } stat1[i][stones] = LOOSE; return false; } static boolean win2(int stones, int i) { int remain; if (stat2[i][stones] != UNKNOWN) return stat2[i][stones] == WON; for (int s = 1; s <= max2[i]; s++) { remain = stones - s; if (remain <= 0) break; if (! win1(remain, (i+1)%N)) { stat2[i][stones] = WON; return true; } } stat2[i][stones] = LOOSE; return false; } static void solve() { stat1 = new int[N][stones+1]; stat2 = new int[N][stones+1]; for (int i = 0; i < N; i++) { stat1[i][1] = LOOSE; stat2[i][1] = LOOSE; for (int s = 2; s <= stones; s++) { stat1[i][s] = UNKNOWN; stat2[i][s] = UNKNOWN; } } int r = win1(stones, 0) ? 1 : 0; System.out.println(r); } public static void main(String args[]) { try { if (args.length > 0) dbg = true; else in = new DataInputStream(new FileInputStream(infile)); while (read()) { solve(); } } catch (Exception e) { e.printStackTrace(); } } }