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 ThreadPoolExecutor defaultThreadPoolExecutor() {
  int poolSize = coresToUse_fixed(), queueSize = 500;
  return new NotifyingBlockingThreadPoolExecutor(poolSize, queueSize, 15, TimeUnit.SECONDS);
}
static int coresToUse_fixed() {
  return max(1, coresToUse());
}



static int max(int a, int b) { return Math.max(a, b); }
static int max(int a, int b, int c) { return max(max(a, b), c); }
static long max(int a, long b) { return Math.max((long) a, b); }
static long max(long a, long b) { return Math.max(a, b); }
static double max(int a, double b) { return Math.max((double) a, b); }
static float max(float a, float b) { return Math.max(a, b); }
static double max(double a, double b) { return Math.max(a, b); }

static int max(Collection<Integer> c) {
  int x = Integer.MIN_VALUE;
  for (int i : c) x = max(x, i);
  return x;
}

static double max(double[] c) {
  if (c.length == 0) return Double.MIN_VALUE;
  double x = c[0];
  for (int i = 1; i < c.length; i++) x = Math.max(x, c[i]);
  return x;
}

static float max(float[] c) {
  if (c.length == 0) return Float.MAX_VALUE;
  float x = c[0];
  for (int i = 1; i < c.length; i++) x = Math.max(x, c[i]);
  return x;
}

static byte max(byte[] c) {
  byte x = -128;
  for (byte d : c) if (d > x) x = d;
  return x;
}

static short max(short[] c) {
  short x = -0x8000;
  for (short d : c) if (d > x) x = d;
  return x;
}

static int max(int[] c) {
  int x = Integer.MIN_VALUE;
  for (int d : c) if (d > x) x = d;
  return x;
}

static ThreadLocal<Integer> coresToUse_tl = new ThreadLocal();

static int coresToUse() {
  { Integer i = coresToUse_tl.get(); if (i != null) return i; }
  return max(1, numberOfCores()-1);
}



static volatile int numberOfCores_value;

static int numberOfCores() {
  if (numberOfCores_value == 0)
    numberOfCores_value = Runtime.getRuntime().availableProcessors();
  return numberOfCores_value;
}



static class NotifyingBlockingThreadPoolExecutor extends ThreadPoolExecutor {

	private AtomicInteger tasksInProcess = new AtomicInteger();

	private Synchronizer synchronizer = new Synchronizer();

	public NotifyingBlockingThreadPoolExecutor(int poolSize, int queueSize, long keepAliveTime, TimeUnit keepAliveTimeUnit, long maxBlockingTime, TimeUnit maxBlockingTimeUnit, Callable<Boolean> blockingTimeCallback) {

		super(poolSize, // Core size
				poolSize, // Max size
				keepAliveTime,
				keepAliveTimeUnit,
				new ArrayBlockingQueue<Runnable>(Math.max(poolSize, queueSize)),
				new BlockThenRunPolicy(maxBlockingTime, maxBlockingTimeUnit, blockingTimeCallback));

		super.allowCoreThreadTimeOut(true);
	}

	public NotifyingBlockingThreadPoolExecutor(int poolSize, int queueSize, long keepAliveTime, TimeUnit unit) {

		super(poolSize, // Core size
				poolSize, // Max size
				keepAliveTime,
				unit,
				new ArrayBlockingQueue<Runnable>(Math.max(poolSize, queueSize)), // not smaller than the poolSize (to avoid redundant threads)
				new BlockThenRunPolicy()); // When super invokes the reject method this class will ensure a blocking try.

		super.allowCoreThreadTimeOut(true); // Time out the core threads.
	}

	@Override
	public void execute(Runnable task) {
		// count a new task in process
		tasksInProcess.incrementAndGet();
		try {
			super.execute(task);
		} catch(RuntimeException e) { // specifically handle RejectedExecutionException  
			tasksInProcess.decrementAndGet();
			throw e;
		} catch(Error e) {
			tasksInProcess.decrementAndGet();
			throw e;
		}
	}

	@Override
	protected void afterExecute(Runnable r, Throwable t) {
		
		super.afterExecute(r, t);

		synchronized(this) {
			tasksInProcess.decrementAndGet();
			if (tasksInProcess.intValue() == 0) {
				synchronizer.signalAll();
			}
		}
	}

	@Override
	public void setCorePoolSize(int corePoolSize) {
		super.setCorePoolSize(corePoolSize);
		super.setMaximumPoolSize(corePoolSize);
	}

	@Override
	public void setMaximumPoolSize(int maximumPoolSize) {
		throw new UnsupportedOperationException("setMaximumPoolSize is not supported.");
	}
	
	public void setRejectedExecutionHandler(RejectedExecutionHandler handler) {
		throw new UnsupportedOperationException("setRejectedExecutionHandler is not allowed on this class.");
	}

	public void await() throws InterruptedException {
		synchronizer.await();
	}

	public boolean await(long timeout, TimeUnit timeUnit) throws InterruptedException {
    	return synchronizer.await(timeout, timeUnit);
	}

	private class Synchronizer {

		private final Lock lock = new ReentrantLock();
		private final Condition done = lock.newCondition();
		private boolean isDone = false;

		private void signalAll() {

			lock.lock();
			try {
				isDone = true;
				done.signalAll();
			}
			finally {
				lock.unlock();
			}
		}

		public void await() throws InterruptedException {

			lock.lock();
			try {
				while (!isDone) {
					done.await();
				}
			}
			finally {
				isDone = false;
				lock.unlock();
			}
		}

		public boolean await(long timeout, TimeUnit timeUnit) throws InterruptedException {

			boolean await_result = false;
			lock.lock();
			boolean localIsDone = false;
			try {
				await_result = done.await(timeout, timeUnit);
			}
			finally {
				localIsDone = isDone;
				isDone = false;
				lock.unlock();
			}
			return await_result && localIsDone;
		}
	}

	private static class BlockThenRunPolicy implements RejectedExecutionHandler {

		private long maxBlockingTime;
		private TimeUnit maxBlockingTimeUnit;
		private Callable<Boolean> blockingTimeCallback;

		public BlockThenRunPolicy(long maxBlockingTime, TimeUnit maxBlockingTimeUnit, Callable<Boolean> blockingTimeCallback) {
			this.maxBlockingTime = maxBlockingTime;
			this.maxBlockingTimeUnit = maxBlockingTimeUnit;
			this.blockingTimeCallback = blockingTimeCallback;
		}

		public BlockThenRunPolicy() {
		}

		@Override
		public void rejectedExecution(Runnable task, ThreadPoolExecutor executor) {           

			BlockingQueue<Runnable> workQueue = executor.getQueue();
			boolean taskSent = false;

			while (!taskSent) {

				if (executor.isShutdown()) {
					throw new RejectedExecutionException(
							"ThreadPoolExecutor has shutdown while attempting to offer a new task.");
				}

				try {
					if(blockingTimeCallback != null) {
						if (workQueue.offer(task, maxBlockingTime, maxBlockingTimeUnit)) {
							taskSent = true;
						}
						else {
							// task was not accepted - call the Callback
							Boolean result = null;
							try {
								result = blockingTimeCallback.call();
							}
							catch(Exception e) {
								throw new RejectedExecutionException(e);
							}
							if(result == false) {
								throw new RejectedExecutionException("User decided to stop waiting for task insertion");                        		
							}
							else {
								continue;
							}
						}

					}
					else {
						workQueue.put(task);
						taskSent = true;
					}                    
				}
				catch (InterruptedException e) {
				}
			}
		}

	}

}
}