/*
import java.util.*;
class LinkedList<E>{
class Node<E>{
private E data;
private Node<E> next;
private int y;
public Node(E data, Node<E> next) {
this.data = data;
this.next =next;
}
}
private Node<E> head;
private Node<E> crnt;
private Node tail;
public void add(char x) {
Node v = new Node(x,null);
v.data = x;
v.next = tail;
head.next = v;
crnt.next = v;
}
public void middlefind() {
}
}
public LinkedList(){
head.next = tail;
crnt.next = tail;
tail = null;
}
}
public class Main{
public Main() {
Scanner s = new Scanner(System.in);
String str = s.nextLine();
LinkedList li = new LinkedList();
char[] chr = new char[str.length()];
for(int i=0; i<str.length(); i++) {
chr[i] = str.charAt(i);
li.add(chr[i]);
}
}
public static void main(String[] args) {
new Main();
}
}
*/
/*
import java.util.*;
class Tree{
class Node<K,V>{
K key;
V data;
Node<K, V> left;
Node<K, V> right;
public Node(K key, V data, Node<K,V> left, Node<K,V> right) {
this.key = key;
this.data =data;
this.left = left;
this.right = right;
}
K getKey() {
return key;
}
V getValue() {
return data;
}
void print() {
System.out.println(data);
}
private Node<K,V> root;
private Comparator<? super K> comparator = null;
}
public class Main{
public Main() {
}
public static void main(String[] args) {
new Main();
}
}
*/
//
//import java.util.*;
//
//public class Main{
// public Main() {
// int k=0;
// int count=0;
// Scanner s = new Scanner(System.in);
// String str =s.nextLine();
//
// for(int i=0; i<)
//
// }
// public static void main(String[] args) {
// new Main();
// }
//}
//void find(int x) {
// find(x*2);
// find(x*2+1);
// print(x);
//}
//
//main {
// find(1);
//}
//}
/*
import java.util.*;
public class Main {
public Main() {
Scanner t = new Scanner(System.in);
String str = t.next();
char chr[] = new char[str.length()+1];
for(int i=0; i<str.length(); i++) {
chr[i+1] = str.charAt(i);
}
int y = str.length();
find(1,y);
}
private void find(int i, int y) {
// TODO Auto-generated method stub
if(i<=y) {
this.find(i*2, y);
System.out.println(i);
this.find(i*2+1, y);
}
}
public static void main(String[] args) {
new Main();
}
}
*/
import java.util.*;
class DbLinkedList<E>{
class Node<E>{
private E data;
private Node<E> prev;
private Node<E> next;
public Node() {
prev = next = this;
}
Node
}
}
public class Main{
public Main() {
}
public static void main(String[] args) {
new Main();
}
}