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 {

static <A> boolean isSortedListByComparator(Collection<A> l, Comparator<A> cmp) {
  Iterator<A> it = iterator(l);
  if (!it.hasNext()) return true;
  A a = it.next();
  while (it.hasNext()) {
    A b = it.next(); 
    if (cmp.compare(a, b) > 0)
      return false;
    a = b;
  }
  return true;
}
static <A> Iterator<A> iterator(Iterable<A> c) {
  return c == null ? emptyIterator() : c.iterator();
}



static Iterator emptyIterator() {
  return Collections.emptyIterator();
}


}