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> List<Pair<A, A>> overlappingPairs_cyclic(List<A> l) {
  List<Pair<A, A>> out = new ArrayList();
  Iterator<A> it = iterator(l);
  if (!it.hasNext()) return out;
  A a = it.next(), first = a;
  while (it.hasNext()) {
    A b = it.next();
    addPair(out, a, b);
    a = b;
  }
  addPair(out, a, first);
  return out;
}
static <A> Iterator<A> iterator(Iterable<A> c) {
  return c == null ? emptyIterator() : c.iterator();
}

static <A, B> void addPair(Collection<Pair<A, B>> c, A a, B b) {
  if (c != null) c.add(pair(a, b));
}



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

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 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 hashCodeFor(Object a) {
  return a == null ? 0 : a.hashCode();
}

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





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

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


}