5ta

import java.util.Collections;
import java.util.LinkedList;
import java.util.Scanner;

class ComplexNumber<T extends Number,U extends Number> implements Comparable<ComplexNumber<T,U>>{
	private T real;
	private U imaginary;
	public ComplexNumber(T _real, U _imaginary){
		real = _real;
		imaginary = _imaginary;
	}
	public T getReal(){
		return real;
	}
	public U getImaginary(){
		return imaginary;
	}
	public double modul(){
		return Math.sqrt(Math.pow(real.doubleValue(),2)+Math.pow(imaginary.doubleValue(),2));
	}
	public String toString(){
		if(imaginary.doubleValue() >= 0) return String.format("%.2f+%.2fi", real.doubleValue(), imaginary.doubleValue());
		return String.format("%.2f%.2fi", real.doubleValue(), imaginary.doubleValue());
	}
	public int compareTo(ComplexNumber<T,U> o){
		if(this.modul() == o.modul()) return 0;
		if(this.modul() > o.modul()) return 1;
		return -1;
	}
}

public class ComplexNumberTest {

	public static void main(String[] args) {
		Scanner jin = new Scanner(System.in);
		int k = jin.nextInt();
		if ( k == 0 ) { //test simple functions int
			int r = jin.nextInt();int i = jin.nextInt();
			ComplexNumber<Integer, Integer> c = new ComplexNumber<Integer, Integer>(r, i);
			System.out.println(c);
			System.out.println(c.getReal());
			System.out.println(c.getImaginary());
			System.out.println(c.modul());
		}
		if ( k == 1 ) { //test simple functions float
			float r = jin.nextFloat();
			float i = jin.nextFloat();
			ComplexNumber<Float, Float> c = new ComplexNumber<Float, Float>(r, i);
			System.out.println(c);
			System.out.println(c.getReal());
			System.out.println(c.getImaginary());
			System.out.println(c.modul());
		}
		if ( k == 2 ) { //compareTo int
			LinkedList<ComplexNumber<Integer,Integer>> complex = new LinkedList<ComplexNumber<Integer,Integer>>();
			while ( jin.hasNextInt() ) {
				int r = jin.nextInt(); int i = jin.nextInt();
				complex.add(new ComplexNumber<Integer, Integer>(r, i));
			}
			System.out.println(complex);
			Collections.sort(complex);
			System.out.println(complex);
		}
		if ( k == 3 ) { //compareTo double
			LinkedList<ComplexNumber<Double,Double>> complex = new LinkedList<ComplexNumber<Double,Double>>();
			while ( jin.hasNextDouble() ) {
				double r = jin.nextDouble(); double i = jin.nextDouble();
				complex.add(new ComplexNumber<Double, Double>(r, i));
			}
			System.out.println(complex);
			Collections.sort(complex);
			System.out.println(complex);
		}
		if ( k == 4 ) { //compareTo mixed
			LinkedList<ComplexNumber<Double,Integer>> complex = new LinkedList<ComplexNumber<Double,Integer>>();
			while ( jin.hasNextDouble() ) {
				double r = jin.nextDouble(); int i = jin.nextInt();
				complex.add(new ComplexNumber<Double, Integer>(r, i));
			}
			System.out.println(complex);
			Collections.sort(complex);
			System.out.println(complex);
		}
	}
}

import java.time.Instant;
import java.time.LocalDateTime;
import java.time.ZoneId;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;
import java.util.Comparator;

class Timestamp <T> implements Comparable<Timestamp<?>>{
	final private LocalDateTime time;
	final private T element;
	public Timestamp(LocalDateTime _time, T _element){
		time = _time;
		element = _element;
	}
	public LocalDateTime getTime(){
		return time;
	}
	public T getElement(){
		return element;
	}
	public int compareTo(Timestamp<?> t){
		if(time.isBefore(t.time)) return -1;
		if(time.isAfter(t.time)) return 1;
		return 0;
	}
	public boolean equals(Object o){
		if(this == o) return true;
		if(o == null) return false;
		if(this.getClass() != o.getClass()) return false;
		Timestamp ts = (Timestamp)o;
		if(!ts.time.isEqual(time)) return false;
		return true;
	}
	public String toString(){
		return time.toString()+" "+element.toString();
	}

}
class Scheduler<T> {
	List<Timestamp<T>> stamps;
	public Scheduler(){
		stamps = new ArrayList<Timestamp<T>>();
	}
	public void add(Timestamp<T> newStamp){
		stamps.add(newStamp);
	}
	public boolean remove(Timestamp<T> delete){
		for(int i = 0; i <stamps.size(); i ++){
			if(delete.equals(stamps.get(i))){
				stamps.remove(i);
				return true;
			}
		}
		return false;
	}
	public Timestamp<T> last(){
		LocalDateTime now = LocalDateTime.now();
		Timestamp<T> ret = null;
		for (int i = 0; i < stamps.size(); i++){
			if(stamps.get(i).getTime().isBefore(now)){
				if(ret == null) ret = stamps.get(i);
				else if(stamps.get(i).getTime().isAfter(ret.getTime()))
					ret = stamps.get(i);
			}
		}
		return ret;
	}
	public Timestamp<T> next(){
		LocalDateTime now = LocalDateTime.now();
		Timestamp<T> ret = null;
		for( int i = 0;i < stamps.size(); i++){
			if(stamps.get(i).getTime().isAfter(now)){
				if(ret == null) ret = stamps.get(i);
				else if ( stamps.get(i).getTime().isBefore(ret.getTime()))
					ret = stamps.get(i);
			}
		}
		return ret;
	}
	public List<Timestamp<T>> getAll(LocalDateTime begin, LocalDateTime end){
		List<Timestamp<T>> ret = new ArrayList<Timestamp<T>>();
		for(int i = 0; i < stamps.size(); i++){
			if(stamps.get(i).getTime().isAfter(begin)&&stamps.get(i).getTime().isBefore(end)){
				ret.add(stamps.get(i));
			}
		}
		return ret;
	}

}

public class SchedulerTest {

    static final LocalDateTime TIME = LocalDateTime.of(2016, 10, 25, 10, 15);

    public static void main(String[] args) {
        Scanner jin = new Scanner(System.in);
        int k = jin.nextInt();
        if (k == 0) { //test Timestamp with String
            Timestamp<String> t = new Timestamp<>(TIME, jin.next());
            System.out.println(t);
            System.out.println(t.getTime());
            System.out.println(t.getElement());
        }
        if (k == 1) { //test Timestamp with ints
            Timestamp<Integer> t1 = new Timestamp<>(TIME, jin.nextInt());
            System.out.println(t1);
            System.out.println(t1.getTime());
            System.out.println(t1.getElement());
            Timestamp<Integer> t2 = new Timestamp<>(TIME.plusDays(10), jin.nextInt());
            System.out.println(t2);
            System.out.println(t2.getTime());
            System.out.println(t2.getElement());
            System.out.println(t1.compareTo(t2));
            System.out.println(t2.compareTo(t1));
            System.out.println(t1.equals(t2));
            System.out.println(t2.equals(t1));
        }
        if (k == 2) {//test Timestamp with String, complex
            Timestamp<String> t1 = new Timestamp<>(ofEpochMS(jin.nextLong()), jin.next());
            System.out.println(t1);
            System.out.println(t1.getTime());
            System.out.println(t1.getElement());
            Timestamp<String> t2 = new Timestamp<>(ofEpochMS(jin.nextLong()), jin.next());
            System.out.println(t2);
            System.out.println(t2.getTime());
            System.out.println(t2.getElement());
            System.out.println(t1.compareTo(t2));
            System.out.println(t2.compareTo(t1));
            System.out.println(t1.equals(t2));
            System.out.println(t2.equals(t1));
        }
        if (k == 3) { //test Scheduler with String
            Scheduler<String> scheduler = new Scheduler<>();
            LocalDateTime now = LocalDateTime.now();
            scheduler.add(new Timestamp<>(now.minusHours(2), jin.next()));
            scheduler.add(new Timestamp<>(now.minusHours(1), jin.next()));
            scheduler.add(new Timestamp<>(now.minusHours(4), jin.next()));
            scheduler.add(new Timestamp<>(now.plusHours(2), jin.next()));
            scheduler.add(new Timestamp<>(now.plusHours(4), jin.next()));
            scheduler.add(new Timestamp<>(now.plusHours(1), jin.next()));
            scheduler.add(new Timestamp<>(now.plusHours(5), jin.next()));
            System.out.println(scheduler.next().getElement());
            System.out.println(scheduler.last().getElement());
            List<Timestamp<String>> result = scheduler.getAll(now.minusHours(3), now.plusHours(4).plusMinutes(15));
            String out = result.stream()
                    .sorted()
                    .map(Timestamp::getElement)
                    .collect(Collectors.joining(", "));
            System.out.println(out);
        }
        if (k == 4) {//test Scheduler with ints complex
            Scheduler<Integer> scheduler = new Scheduler<>();
            int counter = 0;
            ArrayList<Timestamp<Integer>> forRemoval = new ArrayList<>();
            while (jin.hasNextLong()) {
                Timestamp<Integer> ti = new Timestamp<>(ofEpochMS(jin.nextLong()), jin.nextInt());
                if ((counter & 7) == 0) {
                    forRemoval.add(ti);
                }
                scheduler.add(ti);
                ++counter;
            }
            jin.next();

            while (jin.hasNextLong()) {
                LocalDateTime left = ofEpochMS(jin.nextLong());
                LocalDateTime right = ofEpochMS(jin.nextLong());
                List<Timestamp<Integer>> res = scheduler.getAll(left, right);
                Collections.sort(res);
                System.out.println(left + " <: " + print(res) + " >: " + right);
            }
            System.out.println("test");
            List<Timestamp<Integer>> res = scheduler.getAll(ofEpochMS(0), ofEpochMS(Long.MAX_VALUE));
            Collections.sort(res);
            System.out.println(print(res));
            forRemoval.forEach(scheduler::remove);
            res = scheduler.getAll(ofEpochMS(0), ofEpochMS(Long.MAX_VALUE));
            Collections.sort(res);
            System.out.println(print(res));
        }
    }

    private static LocalDateTime ofEpochMS(long ms) {
        return LocalDateTime.ofInstant(Instant.ofEpochMilli(ms), ZoneId.systemDefault());
    }

    private static <T> String print(List<Timestamp<T>> res) {
        if (res == null || res.size() == 0) return "NONE";
        return res.stream()
                .map(each -> each.getElement().toString())
                .collect(Collectors.joining(", "));
    }

}

import java.util.LinkedList;
import java.util.Scanner;

class EmptyQueueException extends Exception{}

class Node<T>{
	T element;
	Node<T> succ;
	public Node(T _element, Node<T> _succ){
		element = _element;
		succ = _succ;
	}
	public T getElement(){
		return element;
	}
	public Node<T> getNext(){
		return succ;
	}
	public void setNext(Node<T> next){
		succ = next;
	}
}
class Queue<T>{
	Node<T> first;
	public Queue(){
		first = null;
	}
	public boolean isEmpty(){
		if (first == null)
			return true;
		return false;
	}
	public void enqueue(T element){
		Node<T> ins = new Node<T>(element, first);
		first = ins;
	}

	public T dequeue() throws EmptyQueueException{
		if(first == null) throw new EmptyQueueException();
		if(first.getNext() == null){
			T ret = first.getElement();
			first = null;
			return ret;
		}
		Node<T> curr = first;
		T ret = null;
		while(curr.getNext().getNext()!=null){
			curr = curr.getNext();
		}
		ret = curr.getNext().getElement();
		curr.setNext(null);
		return ret;
	}

	public T peek() throws EmptyQueueException{
		if(first == null) throw new EmptyQueueException();
		Node<T> curr = first;
		T ret = null;
		while(curr.getNext()!=null){
			curr = curr.getNext();
		}
		ret = curr.getElement();
		return ret;
	}
	public T inspect() throws EmptyQueueException{
		if(first == null) throw new EmptyQueueException();
		return first.getElement();
	}
	public int count(){
		if(first == null) return 0;
		Node<T> curr = first;
		int counter = 1;
		while(curr.getNext()!=null){
			counter++;
			curr = curr.getNext();
		}
		return counter;
	}
}

public class QueueTest {


    public static void main(String[] args) throws EmptyQueueException {
		Scanner jin = new Scanner(System.in);
		int k = jin.nextInt();
		if ( k == 0 ) { //Simple test case with one int element
			int t = jin.nextInt();
			Queue<Integer> queue = new Queue<Integer>();
			System.out.println("Queue empty? - "+queue.isEmpty());
			System.out.println("Queue count? - "+queue.count());
			System.out.println("Queue enqueue "+t);
			queue.enqueue(t);
			System.out.println("Queue empty? - "+queue.isEmpty());
			System.out.println("Queue count? - "+queue.count());
			System.out.println("Queue dequeue? - "+queue.dequeue());
			System.out.println("Queue empty? - "+queue.isEmpty());
			System.out.println("Queue count? - "+queue.count());
		}
		if ( k == 1 ) { //a more complex test with strings
			Queue<String> queue = new Queue<String>();
			int counter = 0;
			while ( jin.hasNextInt() ) {
				String t = jin.next();
				queue.enqueue(t);
				++counter;
			}
			for ( int i = 0 ; i < counter ; ++i ) {
				System.out.println(queue.dequeue());
			}
			queue.enqueue(jin.next());
			System.out.println("Queue inspect? - "+queue.inspect());
			System.out.println("Queue peek? - "+queue.peek());
			queue.enqueue(queue.dequeue());
			queue.enqueue(jin.next());
			System.out.println("Queue inspect? - "+queue.inspect());
			System.out.println("Queue peek? - "+queue.peek());
		}
		if ( k == 2 ) {
			Queue<String> queue = new Queue<String>();
			String next = "";
			int counter = 0;
			while ( true ) {
				next = jin.next();
				if ( next.equals("stop") ) break;
				queue.enqueue(next);
				++counter;
			}
			while ( !queue.isEmpty() ) {
				if ( queue.count()<counter) System.out.print(" ");
				System.out.print(queue.dequeue());
			}
		}
		if ( k == 3 ) { //random testing
			Queue<Double> queue = new Queue<Double>();
			LinkedList<Double> java_queue = new LinkedList<Double>();
			boolean flag = true;
            int n = jin.nextInt();
			for ( int i = 0 ; i < n ; ++i ) {
				double q = Math.random();
				if ( q < 0.5 ) {
					double t = Math.random();
					queue.enqueue(t);
					java_queue.addFirst(t);
				}
				if ( q < 0.8&&q >= 0.5 ) {
					if ( ! java_queue.isEmpty() ) {
						double t1 = java_queue.removeLast();
						double t2 = queue.dequeue();
						flag &= t1==t2;
					}
					else {
						flag &= java_queue.isEmpty()==queue.isEmpty();
					}
				}
				if ( q < 0.9 && q >= 0.8 ) {
					if ( ! java_queue.isEmpty() ) {
						double t1 = java_queue.peekLast();
						double t2 = queue.peek();
						flag &= t1==t2;
					}
					else {
						flag &= java_queue.isEmpty()==queue.isEmpty();
					}
				}
				if ( q < 1 && q >= 0.9 ) {
					if ( ! java_queue.isEmpty() ) {
						double t1 = java_queue.peekFirst();
						double t2 = queue.inspect();
						flag &= t1==t2;
					}
					else {
						flag &= java_queue.isEmpty()==queue.isEmpty();
					}
				}
				flag &= java_queue.size()==queue.count();
			}
			System.out.println("Compared to the control queue the results were the same? - "+flag);
		}
		if ( k == 4 ) { //performance testing
			Queue<Double> queue = new Queue<Double>();
			int n = jin.nextInt();
			for ( int i = 0 ; i < n ; ++i ) {
				if ( Math.random() < 0.5 ) {
					queue.enqueue(Math.random());
				}
				else {
					if ( ! queue.isEmpty() ) {
						queue.dequeue();
					}
				}
			}
			System.out.println("You implementation finished in less then 3 seconds, well done!");
		}
		if ( k == 5 ) { //Exceptions testing
			Queue<String> queue = new Queue<String>();
			try {
				queue.dequeue();
			}
			catch ( Exception e ) {
				System.out.println(e.getClass().getSimpleName());
			}
			try {
				queue.peek();
			}
			catch ( Exception e ) {
				System.out.println(e.getClass().getSimpleName());
			}
			try {
				queue.inspect();
			}
			catch ( Exception e ) {
				System.out.println(e.getClass().getSimpleName());
			}
		}
	}

}

import java.util.Scanner;
import java.util.LinkedList;

class ResizableArray<T>{
	private T[] elements;
	private int numberElements;
	public ResizableArray(){
		elements = (T[]) new Object[10];
		numberElements = 0;
	}
	public void addElement(T element){
		if(numberElements == elements.length){
			T [] temp = (T[]) new Object [elements.length+10];
			for(int i = 0; i < numberElements; i ++){
				temp[i] = elements[i];
			}
			elements = temp;
		}
		elements[numberElements] = element;
		numberElements++;
	}
	public boolean removeElement(T element){
		for(int i = 0; i < numberElements; i++){
			if ( elements[i].equals(element)){
				for(int j = i; j <numberElements-1;j++)
					elements[j] = elements[j+1];
				numberElements--;
				return true;
			}
		}
		return false;
	}
	public boolean contains(T element){
		for(int i = 0; i < numberElements; i++){
			if ( elements[i].equals(element)){
				return true;
			}
		}
		return false;
	}
	public int count(){
		return numberElements;
	}
	public Object[] toArray(){
		T [] ret = (T[]) new Object [numberElements];
		for(int i = 0;i < numberElements; i++){
			ret[i]=elements[i];
		}
		return ret;
	}
	public boolean isEmpty(){
		if(numberElements == 0) return true;
		return false;
	}
	public T elementAt(int index){
		if(index < 0 || index >= numberElements) throw new ArrayIndexOutOfBoundsException();
		return elements[index];
	}
	public static <T> void copyAll(ResizableArray<? super T> dest, ResizableArray<? extends T> src){
		  int c = src.count();
		  for (int i = 0; i < c; i++)
		   dest.addElement(src.elementAt(i));
	}
}

class IntegerArray extends ResizableArray<Integer>{
	public double sum(){
		int ret = 0;
		for(int i = 0; i < this.count(); i++){
			ret += this.elementAt(i);
		}
		return ret;
	}
	public double mean(){
		return this.sum()/this.count();
	}
	public int countNonZero(){
		int counter = 0;
		for(int i = 0; i < this.count(); i++){
			if(this.elementAt(i) != 0)
				counter++;
		}
		return counter;
	}
	public IntegerArray distinct(){
		IntegerArray ret = new IntegerArray();
		for(int i = 0; i < this.count(); i++){
			if(!ret.contains(this.elementAt(i)))
				ret.addElement(this.elementAt(i));
		}
		return ret;
	}
	public IntegerArray increment(int offset){
		IntegerArray ret = new IntegerArray();
		for(int i = 0; i < this.count(); i++){
			ret.addElement(this.elementAt(i)+offset);
		}
		return ret;
	}
}

public class ResizableArrayTest {

	public static void main(String[] args) {
		Scanner jin = new Scanner(System.in);
		int test = jin.nextInt();
		if ( test == 0 ) { //test ResizableArray on ints
			ResizableArray<Integer> a = new ResizableArray<Integer>();
			System.out.println(a.count());
			int first = jin.nextInt();
			a.addElement(first);
			System.out.println(a.count());
			int last = first;
			while ( jin.hasNextInt() ) {
				last = jin.nextInt();
				a.addElement(last);
			}
			System.out.println(a.count());
			System.out.println(a.contains(first));
			System.out.println(a.contains(last));
			System.out.println(a.removeElement(first));
			System.out.println(a.contains(first));
			System.out.println(a.count());
		}
		if ( test == 1 ) { //test ResizableArray on strings
			ResizableArray<String> a = new ResizableArray<String>();
			System.out.println(a.count());
			String first = jin.next();
			a.addElement(first);
			System.out.println(a.count());
			String last = first;
			for ( int i = 0 ; i < 4 ; ++i ) {
				last = jin.next();
				a.addElement(last);
			}
			System.out.println(a.count());
			System.out.println(a.contains(first));
			System.out.println(a.contains(last));
			System.out.println(a.removeElement(first));
			System.out.println(a.contains(first));
			System.out.println(a.count());
			ResizableArray<String> b = new ResizableArray<String>();
			ResizableArray.copyAll(b, a);
			System.out.println(b.count());
			System.out.println(a.count());
			System.out.println(a.contains(first));
			System.out.println(a.contains(last));
			System.out.println(b.contains(first));
			System.out.println(b.contains(last));
			ResizableArray.copyAll(b, a);
			System.out.println(b.count());
			System.out.println(a.count());
			System.out.println(a.contains(first));
			System.out.println(a.contains(last));
			System.out.println(b.contains(first));
			System.out.println(b.contains(last));
			System.out.println(b.removeElement(first));
			System.out.println(b.contains(first));
			System.out.println(b.removeElement(first));
			System.out.println(b.contains(first));

			System.out.println(a.removeElement(first));
			ResizableArray.copyAll(b, a);
			System.out.println(b.count());
			System.out.println(a.count());
			System.out.println(a.contains(first));
			System.out.println(a.contains(last));
			System.out.println(b.contains(first));
			System.out.println(b.contains(last));
		}
		if ( test == 2 ) { //test IntegerArray
			IntegerArray a = new IntegerArray();
			System.out.println(a.isEmpty());
			while ( jin.hasNextInt() ) {
				a.addElement(jin.nextInt());
			}
			jin.next();
			System.out.println(a.sum());
			System.out.println(a.mean());
			System.out.println(a.countNonZero());
			System.out.println(a.count());
			IntegerArray b = a.distinct();
			System.out.println(b.sum());
			IntegerArray c = a.increment(5);
			System.out.println(c.sum());
			if ( a.sum() > 100 )
				ResizableArray.copyAll(a, a);
			else
				ResizableArray.copyAll(a, b);
			System.out.println(a.sum());
			System.out.println(a.removeElement(jin.nextInt()));
			System.out.println(a.sum());
			System.out.println(a.removeElement(jin.nextInt()));
			System.out.println(a.sum());
			System.out.println(a.removeElement(jin.nextInt()));
			System.out.println(a.sum());
			System.out.println(a.contains(jin.nextInt()));
			System.out.println(a.contains(jin.nextInt()));
		}
		if ( test == 3 ) { //test insanely large arrays
			LinkedList<ResizableArray<Integer>> resizable_arrays = new LinkedList<ResizableArray<Integer>>();
			for ( int w = 0 ; w < 500 ; ++w ) {
				ResizableArray<Integer> a = new ResizableArray<Integer>();
				int k =  2000;
				int t =  1000;
				for ( int i = 0 ; i < k ; ++i ) {
					a.addElement(i);
				}

				a.removeElement(0);
				for ( int i = 0 ; i < t ; ++i ) {
					a.removeElement(k-i-1);
				}
				resizable_arrays.add(a);
			}
			System.out.println("You implementation finished in less then 3 seconds, well done!");
		}
	}

}