import java.util.*;
import java.util.zip.*;
import java.util.List;
import java.util.regex.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;
import java.util.concurrent.locks.*;
import javax.swing.*;
import javax.swing.event.*;
import javax.swing.text.*;
import javax.swing.table.*;
import java.io.*;
import java.net.*;
import java.lang.reflect.*;
import java.lang.ref.*;
import java.lang.management.*;
import java.security.*;
import java.security.spec.*;
import java.awt.*;
import java.awt.event.*;
import java.awt.image.*;
import javax.imageio.*;
import java.math.*;
class main {


// returns pair(character range, line) or null if not found
// if no exact match found, return line above
// nav takes a line and returns -1 (move up), 0 (found) or 1 (move down)
static Pair<LongRange, String> binarySearchForLineInTextFile(File file, IF1<String, Integer> nav) {
  long length = l(file);
  int bufSize = 1024;
   RandomAccessFile raf = randomAccessFileForReading(file); try {
  long min = 0, max = length;
  int direction = 0;
  Pair<LongRange, String> possibleResult = null;
  while  (min < max) { ping(); 
    long middle = (min+max)/2;
    long lineStart = raf_findBeginningOfLine(raf, middle, bufSize);
    long lineEnd = raf_findEndOfLine(raf, middle, bufSize);
    
    String line = fromUtf8(raf_readFilePart(raf, lineStart, (int) (lineEnd-1-lineStart)));
    direction = nav.get(line);
    possibleResult = pair(new LongRange(lineStart, lineEnd), line);
    
    if (direction == 0) return possibleResult;
    // asserts are to assure that loop terminates
    if (direction < 0) max = assertLessThan(max, lineStart);
    else min = assertBiggerThan(min, lineEnd);
    
  }
  
  
  if (direction >= 0) return possibleResult;
  
  long lineStart = raf_findBeginningOfLine(raf, min-1, bufSize);
  String line = fromUtf8(raf_readFilePart(raf, lineStart, (int) (min-1-lineStart)));
  
  return pair(new LongRange(lineStart, min), line);
} finally { _close(raf); }}


static int l(Object[] a) { return a == null ? 0 : a.length; }
static int l(boolean[] a) { return a == null ? 0 : a.length; }
static int l(byte[] a) { return a == null ? 0 : a.length; }
static int l(short[] a) { return a == null ? 0 : a.length; }
static int l(long[] a) { return a == null ? 0 : a.length; }
static int l(int[] a) { return a == null ? 0 : a.length; }
static int l(float[] a) { return a == null ? 0 : a.length; }
static int l(double[] a) { return a == null ? 0 : a.length; }
static int l(char[] a) { return a == null ? 0 : a.length; }
static int l(Collection c) { return c == null ? 0 : c.size(); }

static int l(Map m) { return m == null ? 0 : m.size(); }
static int l(CharSequence s) { return s == null ? 0 : s.length(); }
static long l(File f) { return f == null ? 0 : f.length(); }










  static long l(LongRange r) { return r == null ? 0 : r.length(); }

static RandomAccessFile randomAccessFileForReading(File path) { try {
  
    return new RandomAccessFile(path, "r");
  
  
} catch (Exception __e) { throw rethrow(__e); } }

// you can change this function to allow interrupting long calculations from the outside. just throw a RuntimeException.
static boolean ping() { return true; }



static long raf_findBeginningOfLine(RandomAccessFile raf, long pos, int bufSize) { try {
  byte[] buf = new byte[bufSize];
  while (pos > 0) {
    long start = Math.max(pos-bufSize, 0);
    raf.seek(start);
    raf.readFully(buf, 0, (int) Math.min(pos-start, bufSize));
    int idx = lastIndexOf_byteArray(buf, (byte) '\n');
    if (idx >= 0) return start+idx+1;
    pos = start;
  }
  return 0;
} catch (Exception __e) { throw rethrow(__e); } }
static long raf_findEndOfLine(RandomAccessFile raf, long pos, int bufSize) { try {
  byte[] buf = new byte[bufSize];
  long length = raf.length();
  while (pos < length) {
    raf.seek(pos);
    raf.readFully(buf, 0, (int) Math.min(length-pos, bufSize));
    int idx = indexOf_byteArray(buf, (byte) '\n');
    if (idx >= 0) return pos+idx+1;
    pos += bufSize;
  }
  return length;
} catch (Exception __e) { throw rethrow(__e); } }
static String fromUtf8(byte[] bytes) { try {
  return bytes == null ? null : new String(bytes, "UTF-8");
} catch (Exception __e) { throw rethrow(__e); } }
static byte[] raf_readFilePart(RandomAccessFile raf, long start, int l) { try {
  byte[] buf = new byte[l];
  raf.seek(start);
  raf.readFully(buf);
  return buf;
} catch (Exception __e) { throw rethrow(__e); } }
static <A, B> Pair<A, B> pair(A a, B b) {
  return new Pair(a, b);
}

static <A> Pair<A, A> pair(A a) {
  return new Pair(a, a);
}
static <A> A assertLessThan(A a, A b) {
  assertTrue(cmp(b, a) < 0);
  return b;
}
static <A> A assertBiggerThan(A a, A b) {
  assertTrue(cmp(b, a) > 0);
  return b;
}
static void _close(AutoCloseable c) {
  if (c != null) try {
    c.close();
  } catch (Throwable e) {
    // Some classes stupidly throw an exception on double-closing
    if (c instanceof javax.imageio.stream.ImageOutputStream)
      return;
    else throw rethrow(e);
  }
}


static RuntimeException rethrow(Throwable t) {
  
  throw t instanceof RuntimeException ? (RuntimeException) t : new RuntimeException(t);
}

static RuntimeException rethrow(String msg, Throwable t) {
  throw new RuntimeException(msg, t);
}
static int lastIndexOf_byteArray(byte[] a, byte b) {
  for (int i = l(a)-1; i >=0; i--)
    if (a[i] == b)
      return i;
  return -1;
}
static int indexOf_byteArray(byte[] a, byte b) {
  int n = l(a);
  for (int i = 0; i < n; i++)
    if (a[i] == b)
      return i;
  return -1;
}
static void assertTrue(Object o) {
  if (!(eq(o, true) /*|| isTrue(pcallF(o))*/))
    throw fail(str(o));
}
  
static boolean assertTrue(String msg, boolean b) {
  if (!b)
    throw fail(msg);
  return b;
}

static boolean assertTrue(boolean b) {
  if (!b)
    throw fail("oops");
  return b;
}
static int cmp(Number a, Number b) {
  return a == null ? b == null ? 0 : -1 : cmp(a.doubleValue(), b.doubleValue());
}

static int cmp(double a, double b) {
  return a < b ? -1 : a == b ? 0 : 1;
}

static int cmp(Object a, Object b) {
  if (a == null) return b == null ? 0 : -1;
  if (b == null) return 1;
  return ((Comparable) a).compareTo(b);
}


static boolean eq(Object a, Object b) {
  return a == b || (a == null ? b == null : b != null && a.equals(b));
}


static RuntimeException fail() { throw new RuntimeException("fail"); }
static RuntimeException fail(Throwable e) { throw asRuntimeException(e); }
static RuntimeException fail(Object msg) { throw new RuntimeException(String.valueOf(msg)); }
static RuntimeException fail(String msg) { throw new RuntimeException(msg == null ? "" : msg); }
static RuntimeException fail(String msg, Throwable innerException) { throw new RuntimeException(msg, innerException); }

static String str(Object o) {
  return o == null ? "null" : o.toString();
}

static String str(char[] c) {
  return new String(c);
}


static RuntimeException asRuntimeException(Throwable t) {
  
  return t instanceof RuntimeException ? (RuntimeException) t : new RuntimeException(t);
}


final static class LongRange {
  long start, end;
  
  LongRange() {}
  LongRange(long start, long end) {
  this.end = end;
  this.start = start;}
  
  public boolean equals(Object o) {
    if (o instanceof LongRange) return start == ((LongRange) o).start && end == ((LongRange) o).end;
    return false;
  }
  
  public int hashCode() {
    return boostHashCombine(hashOfLong(start), hashOfLong(end));
  }
  
  long length() { return end-start; }
  
  static String _fieldOrder = "start end";
  
  public String toString() { return "[" + start + ";" + end + "]"; }
}static interface IF1<A, B> {
  B get(A a);
}static class Pair<A, B> implements Comparable<Pair<A, B>> {
  A a;
  B b;

  Pair() {}
  Pair(A a, B b) {
  this.b = b;
  this.a = a;}
  
  public int hashCode() {
    return hashCodeFor(a) + 2*hashCodeFor(b);
  }
  
  public boolean equals(Object o) {
    if (o == this) return true;
    if (!(o instanceof Pair)) return false;
    Pair t = (Pair) o;
    return eq(a, t.a) && eq(b, t.b);
  }
  
  public String toString() {
    return "<" + a + ", " + b + ">";
  }
  
  public int compareTo(Pair<A, B> p) {
    if (p == null) return 1;
    int i = ((Comparable<A>) a).compareTo(p.a);
    if (i != 0) return i;
    return ((Comparable<B>) b).compareTo(p.b);
  }
}

static int boostHashCombine(int a, int b) {
  return a ^ (b + 0x9e3779b9 + (a << 6) + (a >> 2));
}
static int hashOfLong(long l) {
  return Long.hashCode(l);
}
static int hashCodeFor(Object a) {
  return a == null ? 0 : a.hashCode();
}

}