hamadu

import java.io.IOException;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
	
	static final long MOD = 1000000007;

hamadu

bool DEBUG = false;
double TLE = 30.0;

long _xtime = 30000;
int _maxTurn = 10000;
bool _debug = false;

#include <vector>
#include <list>
#include <map>

hamadu

import qualified Data.Map as Map

type Memo = Map.Map (Int,Int) Int

combination :: Memo -> Int -> Int -> (Int, Memo)
combination memo n r
  | r == 0    = (1, memo)
  | n == r    = (1, memo)
  | otherwise =
      case Map.lookup (n,r) memo of

hamadu

# Tree+Heap=Treap
class Treap
  attr_accessor :value, :left, :right, :priority

  # 空の頂点
  def self.empty()
    obj = self.new
    obj.value = -1
    obj.priority = rand(0.0...1.0)
    obj

hamadu

# ランダム挿入二分探索木
class RandomizedBinarySearchTree
  attr_accessor :value, :left, :right
  attr_accessor :count
  
  # 空の頂点
  def self.empty
    obj = self.new
    obj.value = -1
    obj.count = 0

hamadu

function uni_html_link($name, $module = '', $action = '', $param = array(), $class = ''){
  $str = $module . '/' . $action;
  if (count($param) > 0) {
    $str .= '?';
    foreach ($param as $key => $value) {
      $str .= $key . '=' . $value . '&';
    }
    $str = substr($str, 0, -1);
  }
  $url = url_for($str);

hamadu

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

public class ProblemA {


	public static void main(String[] args) throws IOException {
		BufferedReader s = new BufferedReader(new InputStreamReader(System.in));

hamadu

26
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
29
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 25 25 25 25 25
31
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 20 20 20 20 20 20
1
25
30
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 25 25 25 25 25

hamadu

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

public class ProblemA {


	public static void main(String[] args) throws IOException {
		BufferedReader s = new BufferedReader(new InputStreamReader(System.in));

hamadu

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

public class ProblemA {


	public static void main(String[] args) throws IOException {
		BufferedReader s = new BufferedReader(new InputStreamReader(System.in));