akhauriyash/Code-Regression huggingface dataset:
package main

import (
    "bufio"
    "fmt"
    "os"
)

var reader *bufio.Reader = bufio.NewReader(os.Stdin)
var writer *bufio.Writer = bufio.NewWriter(os.Stdout)
func printf(f string, a ...interface{}) { fmt.Fprintf(writer, f, a...) }
func scanf(f string, a ...interface{}) { fmt.Fscanf(reader, f, a...) }

func main() {
    defer writer.Flush()
    var n int
    scanf("%d\n", &n)
    r := n % 10
    if r == 3 {
        printf("bon\n")
    } else if r == 0 || r == 1 || r == 6 || r == 8 {
        printf("pon\n")
    } else {
        printf("hon\n")
    }
}

Measured memory_bytes: 1828
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lvector vector<ll>
#define cvector vector<char>
#define svector vector<string>
#define lque queue<ll>
#define lpque priority_queue<ll>
#define dlpque priority_queue<ll,lvector,greater<ll>>
#define P pair<ll,ll>
#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()
#define rep(i,n) for(ll i=0; i<n; ++i)
#define print(a) cout << (a) << endl

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n,m,a,b;cin>>n>>m;
  vector<lvector> G(n);
  rep(i,m) {
    cin>>a>>b;a--,b--;
    G[a].emplace_back(b);
    G[b].emplace_back(a);
  }
  ll pos;
  lque que;que.push(0);
  lvector ans(n,-1);
  while(que.size()) {
    lque tmp;
    while(que.size()) {
      pos=que.front();que.pop();
      for(ll next:G[pos]) {
        if(ans[next]>-1) continue;
        ans[next]=pos;
        tmp.push(next);
      }
    }
    que=tmp;
  }
  print("Yes");
  rep(i,n-1) print(ans[i+1]+1);
  return 0;
}

Measured memory_bytes: 13604
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from collections import Counter

h,w,m=nii()

h_bomb=[0 for i in range(h)]
w_bomb=[0 for i in range(w)]

l=set()
for i in range(m):
  th,tw=nii()
  th-=1
  tw-=1
  h_bomb[th]+=1
  w_bomb[tw]+=1
  l.add((th,tw))

h_max=max(h_bomb)
w_max=max(w_bomb)

h_cand=[]
w_cand=[]

for i in range(len(h_bomb)):
  if h_bomb[i]==h_max:
    h_cand.append(i)

for i in range(len(w_bomb)):
  if w_bomb[i]==w_max:
    w_cand.append(i)

for i in h_cand:
  for j in w_cand:
    if (i,j) not in l:
      print(h_max+w_max)
      exit()

print(h_max+w_max-1)

Measured memory_bytes: 166688
#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
    while(a && b){
        a%=b;
        if(a==0)break;
        b%=a;
    }
    return a+b;
}
int main(){
    int n,x=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int g=gcd(i,j);
            for(int k=1;k<=n;k++){
                x+=gcd(g,k);
            }
        }
    }
    cout<<x<<endl;
    return 0;
}

Measured memory_bytes: 3636
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
int main()
{
	LL a,b;
	char str[3];
	while(~scanf("%lld %s %lld",&a,str,&b))
	{
		LL c;
		if(str[0]=='+')
			c=a+b;
		else
			c=a-b;
		printf("%lld\n",c);
	}
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int const nax = 5010;
const int mod = 1e9 + 7;

void plusle (int &a, int b) {
    if (( a += b) >= mod ) a -= mod ;
}

void minun (int &a, int b) {
    if ((a -= b) < 0) a += mod ;
}

int add (int a, int b) {
    return (( a += b ) >= mod ) ? a - mod  : a;
}

int sub (int a, int b) {
    return (( a -= b) < 0) ? a + mod : a;
}

int mul (int a, int b) {
    return 1LL * a * b % mod;
}

int power (int a, int b) {
    int res = 1;
    for (; b > 0 ; b >>= 1 , a = mul(a, a))
        if (b & 1) res = mul(res, a);
    return res ;
}

struct DSU {
    int par[nax];
    int sz[nax];
    int n;

    DSU (int n) {
        this->n = n;
        iota(par + 1, par + 1 + n, 1);
        fill(sz + 1, sz + 1 + n, 1);
    }

    int find (int x) {
        return x == par[x] ? x : par[x] = find(par[x]);
    }

    bool unite (int x, int y) {
        x = find(x), y = find(y);

        if (x == y) return false;

        if (sz[x] < sz[y]) swap(x, y);
        sz[x] += sz[y];
        par[y] = x;

        return true;
    }
};

int n;
int p[nax];
int cyc;
vector <int> a[nax];
int sz[nax]; /// sz for each component
bool white_only;
bool vis[nax];
int ct_comp;
int topSZ;
int b[nax];
int deg;
int fac[nax];

void mul_by (int s) {
    /// multiply by sx + 1
    /**
    a_n
    */
    ++ deg;
    for (int i = deg; i > 0 ; -- i) {
        b[i] = add(b[i], mul(b[i - 1], s));
    }
}

void dfs (int nod) {
    vis[nod] = true;
    if (p[nod] == -1) white_only = false;
    ++ ct_comp;

    for (int i : a[nod]) {
        if (!vis[i]) dfs(i);
    }
}

int main () {

    scanf("%d", &n);

    DSU ds(n);

    int k = 0;
    b[0] = 1;

    fac[0] = 1;

    for (int i = 1 ; i <= n ; ++ i) {
        scanf("%d", p + i);

        fac[i] = mul(fac[i - 1], i);

        if (p[i] == -1) {
            ++ k;
            continue;
        }

        if (!ds.unite(i, p[i])) {
            ++ cyc;
        }

        a[i].push_back(p[i]);
        a[p[i]].push_back(i);
    }

    int self = 0;

    for (int i = 1 ; i <= n ; ++ i) {
        if (vis[i]) continue;
        white_only = true;
        ct_comp = 0;
        dfs(i);
        if (white_only) continue;
        sz[++ topSZ] = ct_comp;
        mul_by(ct_comp);

        self += ct_comp - 1;
    }

    int ans = mul(n - cyc, power(n - 1, k));

    for (int i = 2 ; i <= k ; ++ i) {
        /// cycle of lenght i
        int coeff = b[i];

        int to_sub = mul(coeff, fac[i - 1]);
        to_sub = mul(to_sub, power(n - 1, k - i));

        minun(ans, to_sub);
    }

    self = mul(self, power(n - 1, k - 1));
    minun(ans, self);

    printf("%d\n", ans);




}
/*
    Good Luck
        -Lucina
*/


Measured memory_bytes: 4188
#include<bits/stdc++.h>
using namespace std;
signed main(){
  int n,b,f,r,v;
  int room[10][10][100]={};
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>b>>f>>r>>v;
    room[b-1][f-1][r-1]+=v;
  }
  for(int i=0;i<4;i++){
    for(int j=0;j<3;j++){
      for(int k=0;k<10;k++){
	cout<<' '<<room[i][j][k];
	if(k==9)
	  cout<<'\n';
      }
      if(j==2 && i!=3)
	cout<<"####################"<<'\n';
    }
  }
  return 0;
}
      



Measured memory_bytes: 3156
//BINARY_BOY!!
//THINK TWICE CODE ONCE { TRUE }
// #####   ###  ##   #   ###   #####   #   #  #####	#####
// #    #   #   # #  #  #   #  #    #   # #   #	#	#	#	
// #####    #   #  # #  #####  #####     #    #####	#	#		
// #    #   #   #   ##  #   #  #   #     #    #	#	#	#
// #####   ###  #    #  #   #  #    #    #    #####	#####	
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXN = 10000 + 5;
vector < pair < int  , pair < int , int > > > v ;
vector< int > v2 [ MAXN ];
int n , m, sum = 0, num [ MAXN ];
bool cmd(pair < int , pair<int , int> > p1 , pair < int , pair<int , int> > p2 )
{
	return p1.first < p2.first;
}
int main() {
	ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0);
	cin >> n >> m;
	for(int i = 0 ; i < m ; i++)
	{
		int a , b, c;
		cin >> a >> b >> c;
		v.push_back(make_pair(c , make_pair(a , b)));
	}
	sort(v.begin() , v.end() , cmd);
	for(int i = 0 ; i <= n ; i++)
	{
		v2[ i ].push_back(i);
		num [ i ] = i;
	}
	for(int i = 0 , j = 0 ; i < v.size() && j < n - 1; i++)
	{
		if(num [ v [ i ].second.first ] != num [ v [ i ].second.second ] )
		{
			sum += v [ i ].first;
			j++;
			if(v2 [ num [v [ i ].second.first ]].size() <  v2 [num[ v [ i ].second.second ]].size())
			{
				for(int f = 0 , l = v2 [ num [v [ i ].second.first ] ].size() , k = num [v [ i ].second.first]; f < l ; f++)
				{
					v2 [ num [v [ i ].second.second ] ].push_back(v2 [ k ][ f ]);
					num [v2 [ k ][ f ]] = num [v [ i ].second.second];
				}
			}
			else {
				for(int f = 0 , l = v2 [ num [v [ i ].second.second ] ].size() , k = num [v [ i ].second.second] ; f < l ; f++)
				{
					v2 [ num [v [ i ].second.first] ].push_back(v2 [ k ][ f ]);
					num [v2 [ k ][ f ]] = num [v [ i ].second.first];
				}
			}
		}
	}
	cout << sum << endl;
}

Measured memory_bytes: 4800
#include <bits/stdc++.h>
using namespace std;
 
int main(){
    int A,B,C;
    long long K;
    cin >> A >> B >> C >> K;

    if(K%2){
        cout << -(A-B) << endl;
    }else{
        cout << (A-B) << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define prArr(Arr,n) for(int _=0;_<n;_++)   cout<<(Arr)[_]<<" ";
#define f first
#define s second
using namespace std;
const int INF=(int)0x3f3f3f3f;
const int MOD=(int)1e9+7;
const double eps=1e-9;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    cout<<3*n*n;
    return 0;
}


Measured memory_bytes: 3612
#include <stdio.h>

int main(){
  int c[4][4];
  int d[4][4];
  int i,j;
  for(i=0;i<3;i++)
    for(j=0;j<3;j++)
      scanf("%d",&c[i][j]);
  for(i=0;i<3;i++)
    for(j=0;j<2;j++)
      d[i][j]=c[i][j+1]-c[i][j];
  if(d[0][0]==d[1][0] && d[0][1]==d[1][1] && d[1][0]==d[2][0] && d[1][1]==d[2][1])
    printf("Yes\n");
  else
    printf("No\n");
  
  return 0;
}

Measured memory_bytes: 128
#include<iostream>
using namespace std;

int A,B,C;

int main(){

	cin >> A >> B >> C;
  
  	if( A == 5 && B == 5 && C == 7 ) cout << "YES" << endl;
	else if( A == 5 && B == 7 && C == 5 ) cout << "YES" << endl;
	else if( A == 7 && B == 5 && C == 5 ) cout << "YES" << endl;
	else cout << "NO" << endl;
  
}

Measured memory_bytes: 256
#include<iostream>
#include<string>

bool is_akihabara(std::string s){
    bool check = false;

    if(s == "AKIHABARA") check = true;

    else if (s == "KIHABARA") check = true;
    else if (s == "AKIHBARA") check = true;
    else if (s == "AKIHABRA") check = true;
    else if (s == "AKIHABAR") check = true;

    else if (s == "KIHBARA") check = true;
    else if (s == "KIHABRA") check = true;
    else if (s == "KIHABAR") check = true;
    else if (s == "AKIHBRA") check = true;
    else if (s == "AKIHBAR") check = true;
    else if (s == "AKIHABR") check = true;

    else if (s == "KIHBRA") check = true;
    else if (s == "KIHBAR") check = true;
    else if (s == "KIHABR") check = true;
    else if (s == "AKIHBR") check = true;
    
    else if (s == "KIHBR") check = true;

    return check;
}

int main(void){
    std::string s;
    std::cin >> s;

    if(is_akihabara(s)){
        std::cout << "YES" << std::endl;
        return 0;
    }
    else{
        std::cout << "NO" << std::endl;
        return 0;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
using ll = int64_t;
constexpr ll mod = ll(1e9 + 7);
 
int main () {
  ios::sync_with_stdio(0); cin.tie(0);
 
  int h,w,k;
  cin >> h >> w >> k;
  vector<vector<int>> M(h, vector<int>(w));
  for (auto& row : M) for (auto& x : row) {
      char z;
      cin >> z;
      x = (z == '#');
    }
  int n = h+w;
  ll ans = 0;
  for (int state = 0; state < (1 << n); ++state) {
    int state_y = state >> w;
    int state_x = state & ((1 << w)-1);
    int sum = 0;
    for (int y = 0; y < h; ++y) {
      if ((state_y>>y)&1) continue;
      for (int x = 0; x < w; ++x) {
        if ((state_x>>x)&1) continue;
        sum += M[y][x];
      }
    }
    ans += sum == k;
  }
  cout << ans << endl;
  
}


Measured memory_bytes: 3672
// https://atcoder.jp/contests/abc109/tasks/abc109_c

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

int main() {
    long n, x;
    vector<bool> v1;
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    cin >> n >> x;
    int pos[n];

    for (int i = 0; i < n; i++) {
        cin >> pos[i];
    }
    sort(pos, pos + n);

    int ans = abs(x - pos[0]);
    // 開始時点からの差分
    for (int i = 1; i < n; i++) {
        ans = gcd(ans, abs(x - pos[i]));
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 640
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
using namespace std;
int main() {
  double w,h,x,y;
  cin >> w >> h >> x >> y;
  cout << fixed << setprecision(10) << w*h/2 << " ";
  if(x*2==w&&y*2==h) {
    cout << 1;
  }
  else {
    cout << 0;
  }
  cout << endl;
}

Measured memory_bytes: 256
using System;
using System.Linq;

namespace MSPC
{
    class Program
    {
        static void Main(string[] args)
        {
            string s = Console.ReadLine();

            if (8 <= s.Count(x => x == 'x'))
                Console.WriteLine("NO");
            else
                Console.WriteLine("YES");
        }
    }
}


Measured memory_bytes: 13268
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a

# Union Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# 約数生成
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors


inf = 10 ** 18
mod = 10 ** 9 + 7

n,m,k = lr()
for i in range(n+1):
    for j in range(m+1):
        tmp = (m-j)*i + (n-i)*j
        if tmp == k:
            print('Yes')
            sys.exit()
print('No')

Measured memory_bytes: 77504
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.solve();
    }
    public void solve() {
        Scanner scan = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int N = scan.nextInt();
        int count_even = N / 2;
        int count_odd = N / 2 + (N % 2 == 1 ? 1 : 0);
        double ans = (double) count_odd / N;
        System.out.printf("%.7f", ans);
    }
}


Measured memory_bytes: 24916
a,b = map(int, input().split())
w = 100
h = 20
grid = []
for _ in range(h):#黒
    grid.append(['#' for i in range(w)])
for _ in range(h):#白
    grid.append(['.' for i in range(w)])
n = 0
for i in range(0,a-1):
    if i % 50 == 0 and i != 0:
        n += 2
    grid[n][2*(i % 50)] = '.'

n = h+1
for i in range(0,b-1):
    if i % 50 == 0 and i != 0:
        n += 2
    grid[n][2*(i % 50)] = '#'

print(2*h,w)
for i in range(2*h):
    print(''.join(grid[i]))


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define pb push_back
#define mp make_pair
#define f(i,a,n) for(int i=a ; i<n ; i++)
#define all(c) (c).begin(),(c).end()
#define F first
#define S second
#define fast ios:: sync_with_stdio(false),cin.tie(nullptr);
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
typedef vector<pii> vpi;

const int inf = 1e9;
const int inf64 = 1e18;
const int MOD = inf + 7;
const ld PI = acos(-1.0);

int32_t main(){
	fast;
	string s;
	cin >> s;
	for(auto &x : s)
	{
		if(x == ',')
			x = ' ';
	}
	cout << s;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define debug(x) cerr<<#x<<" -> "<<x<<'\n'
#define debug2(x,y) cerr<<#x<<" -> "<<x<<" "<<#y<<" -> "<<y<<'\n'
#define debug3(x,y,z) cerr<<#x<<" -> "<<x<<" "<<#y<<" -> "<<y<<" "<<#z<<" -> "<<z<<'\n'

 
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;

using ordered_set = tree<ll , null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>;

template<typename T>
struct CMP {
	bool operator() (const T& lhs, const T& rhs) const{
		return lhs < rhs;
	}
};

template <typename T>
T power(T a, T n){
	T res = 1;
	while(n > 0){
		if(n & 1) res = (res * a);
		a = (a * a);
		n >>= 1;
	}
	
	return res;
}

template <typename T>
T power(T a, T n, long long mm){
	T res = 1;
	while(n > 0){
		if(n & 1) res = (res * a) % mm;
		a = (a * a) % mm;
		n >>= 1;
	}
	
	return res;
}

const ll N = 2e5+7;
const ll MOD = 1e9+7;
const ll INF = 2e14+7;

pair<ll, ll> arr[105];
ll dp[N][105];


void testcase(){
	int n;
	ll w;
	cin>>n>>w;
	for(int i = 1; i <= n; i++) cin>>arr[i].fi>>arr[i].se;
	
	for(int i = 0; i < N; i++){
		for(int j = 0; j <= n; j++){
			dp[i][j] = INF;
		}
	}
	
	/*for(int i = 0; i < N; i++){
		dp[i][0] = 0;
	}*/
	
	for(int i = 0; i <= n; i++){
		dp[0][i] = 0;
	}
	
	
	for(int i = 1; i <= n; i++){
		
		for(int j = 0; j < N; j++){
			dp[j][i] = dp[j][i - 1];
		}
		
		for(int j = arr[i].se; j < N; j++){
			
			dp[j][i] = min(dp[j][i], arr[i].fi + dp[j - arr[i].se][i - 1]);
			
		}
	}
	
	ll ans = -1;
	
	for(int i = N - 1; i; i--){
		if(dp[i][n] <= w){
			ans = i;
			break;
		}
	}
	
	cout<<ans<<'\n';
	
}

signed main(){
	fast;
	
	int t = 1;
	//cin>>t;
	while(t--){
		testcase();
	}
	
	return 0;
}


Measured memory_bytes: 164352
#include <bits/stdc++.h>
using namespace std;

int main(){
  int n;
  cin >> n;
  if(n==25){
    cout << "Christmas" << endl;
  }else if(n==24){
    cout << "Christmas Eve" << endl;
  }else if(n==23){
    cout << "Christmas Eve Eve" << endl; 
  }else if(n==22){
    cout << "Christmas Eve  Eve Eve" << endl;
  }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
 
using namespace std;
 
#define all(a) a.begin(),a.end()
#define F first
#define S second
#define pb push_back
#define ll long long
#define vi vector<int>
#define pi pair<int,int>
#define mp make_pair
 
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int mod=1e9+7;
			
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename A,typename B> istream& operator>>(istream&,pair<A,B>&);
template<typename A> istream& operator>>(istream&,vector<A>&);
void add(int&,int);
int mul(int,int);
int powz(int,int);
int sub(int,int);
template<typename A> ostream& operator<<(ostream&,vector<A>&);
 
const int N=1000001;
int st[4*N];

void update(int v,int tl,int tr,int ind){
	if(tl==tr){
		st[v]++;
		return;
	}
	int mid=(tl+tr)/2;
	if(ind<=mid){
		update(2*v,tl,mid,ind);
	}
	else{
		update(2*v+1,mid+1,tr,ind);
	}
	st[v]=st[2*v]+st[2*v+1];
}

void solve(){
	int n;
	cin>>n;
	vi a(n);
	cin>>a;
	multiset<int>en;
	for(int i=0;i<n;i++){
		if(en.empty()){
			en.insert(a[i]);
		}
		else{
			auto it=en.lower_bound(a[i]);
			    if(it==en.begin()&&(*it>=a[i])){
					en.insert(a[i]);
				}
				else if(it==en.begin()){
					en.erase(it);
				en.insert(a[i]);
				}
				else{
				it--;
				en.erase(it);
				en.insert(a[i]);
			}
			
			
		}
	}
	cout<<en.size();
	
	
}
 
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int tc=1;
	//~ cin>>tc;
	for(int _=0;_<tc;_++){
		solve();
		if(_!=tc-1)
		cout<<"\n";
	}
}
 
int mul(int a,int b)
{
	return ((a)*1ll*(b))%mod;
}
 
void add(int &a,int b)
{
	a+=b;
	if(a>=mod)a-=mod;
}
 
int sub(int a,int b){
	a-=b;
	if(a<0){
		a+=mod;
	}
	return a;
}
 
int powz(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)res=mul(res,a);
		b/=2;
		a=mul(a,a);
	}
	return res;
}
 
template <typename A, typename B>
istream& operator>>(istream& input,pair<A,B>& x) {
	input>>x.F>>x.S;
	return input;
}
 
template <typename A>
istream& operator>>(istream& input,vector<A>& x) {
	for(auto& i:x)
		input>>i;
	return input;
}
 
template<typename A>
ostream& operator<<(ostream& output,vector<A>& x) {
	for(auto& i:x)
	    output<<i<<' ';
	return output;
}


Measured memory_bytes: 5376
// Code Forces
#include<bits/stdc++.h>
#define ll long long int
#define MOD 1000000007
#define pi 3.1415926535
#define fi first
#define se second
#define vec vector
#define str string
#define FOR(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define fast ios_base::sync_with_stdio(false);  cin.tie(NULL);
#define dvec(v) vec < ll > v
#define sortA(v) sort(v.begin(),v.end())
#define sortD(v) sort(v.begin(),v.end(),greater <int> ())

using namespace std;

int main(){
    fast
    ll a=0,b=0,res=0;
    cin>>a>>b;
    if(a>1&&b>1)
        res=(a*(a-1)/2)+(b*(b-1)/2);
    else if(a>1&&((b==1)||(b==0)))
        res=(a*(a-1)/2);
    else
        res=(b*(b-1)/2);
    cout<<res;
    // my code
    return 0;
}

Measured memory_bytes: 256
import scala.io.StdIn.readInt

object Main {
  val r = Array(2,3,5,7)

  def pow(x:Long, y:Long, z:Long):Long = {

    def multi(m:Long, n:Long) = { ( (m%z) * (n%z) ) % z }

    def pow2(m:Long, n:Long, odd:Long, b:Long):Long = {
      n match {
        case 0 => 1
        case 1 => multi(m, odd)
        case _ =>
          pow2(multi(m,m), n/2, (if(n%2==1) multi(odd, b) else odd), multi(b,b))
      }
    }
    pow2(x, y, 1, x)
  }

  def twoPow(d:Int,s:Int):(Int,Int) = {
    if(d%2 == 1) (d,s)
    else twoPow(d>>1,s+1)
  }

  def maybePrime(i:Int,d:Int,s:Int, n:Int):Boolean = {
    if(i>3) true
    else {
      val a = r(i)
      val x = pow(a,d,n)

      if(x==1 || x==n-1) maybePrime(i+1,d,s,n)
      else repeat(s-1,x*x%n, i, d, s, n)
    }
  }

  def repeat(j:Int, x:Long, i:Int, d:Int, s:Int, n:Int):Boolean = {
    if(j==0) false
    else if(x==1) false
    else if(x==n-1) maybePrime(i+1,d,s,n)
    else repeat(j-1,x*x%n,i,d,s,n)
  }

  def isPrime(n:Int):Boolean = {
    if(n<5000) (2 to Math.sqrt(n).toInt).forall(n%_ != 0)
    else if(n%2==0) false
    else {
      val (d,s) = twoPow(n-1,0)
      maybePrime(0,d,s,n)
    }
  }

  def main(args:Array[String]) = {
    val n = readInt
    println((0 until n).count{ _=> isPrime(readInt) })
  }
}

Measured memory_bytes: 50504
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;

#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define sz(x) int(x.size())

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const double PI=3.14159265358979323846;

int mod = 1e9+7;
int INF = 1e9+7;
// const long long INF = 1LL<<60;


int main(){
  int N, M;
  cin >> N >> M;
  vector<int> P(M), Y(M);
  rep(i, M){
    cin >> P[i] >> Y[i];
    --P[i];
  }
  vector<vector<int>> v(N);
  rep(i, M) v[P[i]].push_back(Y[i]);

  rep(i, N){
    sort(v[i].begin(), v[i].end());
    v[i].erase(unique(v[i].begin(), v[i].end()), v[i].end());
  }

  rep(i, M){
    int pid = P[i];
    printf("%06d", pid + 1);
    int id = lower_bound(v[pid].begin(), v[pid].end(), Y[i]) - v[pid].begin() + 1;
    printf("%06d\n", id);
  }

  return 0;
}


Measured memory_bytes: 7808
#include <iostream>
#include <cstdio>
using namespace std;

int main(void){
  int h,m,s;
  int rest, tri;
  
  while (cin >> h >> m >> s){
    if (h<0) break;
    rest = 2*3600 - (h*3600+m*60+s);
    tri = rest * 3;
    s = rest%60; rest/=60;
    m = rest%60; rest/=60;
    h = rest;
    printf("%02d:%02d:%02d\n", h, m, s);
    s = tri%60; tri/=60;
    m = tri%60; tri/=60;
    h = tri;
    printf("%02d:%02d:%02d\n", h, m, s);
  }
  return 0;
}


Measured memory_bytes: 3164
#include <bits/stdc++.h>

#define EPS (1e-10)
#define rep(i, a, b) for (int i = a; i < (int)(b); ++i)
#define rrep(i, a, b) for (int i = b - 1; i >= (int)(a); --i)
#define all(a) a.begin(), a.end()

using namespace std;
using ll = long long;
using vi = vector<int>;
using vb = vector<bool>;
using vll = vector<ll>;
using vd = vector<double>;
using vvi = vector<vi>;
using vvb = vector<vb>;

constexpr int MOD = 1000000007;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n;
    cin >> n;

    vi l(n);
    rep(i, 0, n) { cin >> l[i]; }

    sort(all(l));

    int ans = 0;
    rrep(i, 2, n) {
        rrep(b, 1, i) {
            int a = 0;
            while (a < b && l[a] + l[b] <= l[i]) { ++a; }
            ans += b - a;
        }
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using uint = unsigned int;
#define rep(i,n) for(int i=0;i<int(n);i++)
#define rep1(i,n) for(int i=1;i<=int(n);i++)
#define per(i,n) for(int i=int(n)-1;i>=0;i--)
#define per1(i,n) for(int i=int(n);i>0;i--)
#define all(c) c.begin(),c.end()
#define si(x) int(x.size())
#define pb emplace_back
#define fs first
#define sc second
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
template<class T,class U> void chmax(T& x, U y){if(x<y) x=y;}
template<class T,class U> void chmin(T& x, U y){if(y<x) x=y;}
template<class T> void mkuni(V<T>& v){sort(all(v));v.erase(unique(all(v)),v.end());}
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
	return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
	o<<"{";
	for(const T& v:vc) o<<v<<",";
	o<<"}";
	return o;
}
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

#ifdef LOCAL
#define show(x) cerr << "LINE" << __LINE__ << " : " << #x << " = " << (x) << endl
void dmpr(ostream& os){os<<endl;}
template<class T,class... Args>
void dmpr(ostream&os,const T&t,const Args&... args){
	os<<t<<" ~ ";
	dmpr(os,args...);
}
#define shows(...) cerr << "LINE" << __LINE__ << " : ";dmpr(cerr,##__VA_ARGS__)
#define dump(x) cerr << "LINE" << __LINE__ << " : " << #x << " = {";  \
	for(auto v: x) cerr << v << ","; cerr << "}" << endl;
#else
#define show(x) void(0)
#define dump(x) void(0)
#define shows(...) void(0)
#endif

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);		//DON'T USE scanf/printf/puts !!
	cout << fixed << setprecision(20);

	int A,B; cin >> A >> B;
	int H = 100, W = 100;
	V<string> s(H,string(W,'.'));
	rep(i,H){
		rep(j,W) s[i][j] = (i<H/2 ? '.' : '#');
	}
	A--,B--;
	rep(i,H/2) rep(j,W/2){
		if(B){
			s[i*2][j*2] = '#';
			B--;
		}
	}
	rep(i,H/2) rep(j,W/2){
		if(A){
			s[H-1-i*2][j*2] = '.';
			A--;
		}
	}
	cout << H << " " << W << endl;
	rep(i,H) cout << s[i] << endl;
}


Measured memory_bytes: 256
/*input
10 4 8

*/
#include "bits/stdc++.h"
#define pb push_back
#define ll long long
using namespace std;
#define N 400005
#define mp make_pair
//#define int long long
vector<int> v[2005];
int dist[2005], vis[2005], cnt[2005];


void bfs(int start) {
	queue<pair<int,int> > Q;
	Q.push(mp(start, 0));

	while(!Q.empty()) {
		int node = Q.front().first;
		int dista = Q.front().second;
		Q.pop();
		if(vis[node]) continue;
		vis[node] =1;

		dist[node] = dista;

		for(auto it: v[node]) {
			if(!vis[it])
				Q.push(mp(it, 1+ dista));
		}
	}
}
signed main()
{
	int n, x, y;
	cin >>n >> x >>y;

	for(int i=1 ; i<n; i++){
		v[i].push_back(i+1);
		v[i+1].push_back(i);}

	v[x].push_back(y);
	v[y].push_back(x);
	memset(cnt,0,sizeof(cnt));

	//cout<<2<<endl;

	for(int i=1;i<=n;i++) {
		for(int j=1;j<=n;j++){
			dist[j] = 1e9; vis[j] = 0;}
		
		bfs(i);

		for(int j=1;j<=n;j++)
			cnt[dist[j]]++;
	}

	//out<<2<<endl;
	for(int i=1; i<n; i++)
		cout<<cnt[i]/2 <<endl;

}

Measured memory_bytes: 384
#include <math.h>
#include <iostream>
#include <ios>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <string>

#define YES "YES"
#define NO "NO"
#define space ' '

using namespace std;

void func();

int main(void)
{
	
	func();

	return 0;
}


void func()
{
	int n, debt;

	debt = 100000;

	cin >> n;
	while (n-- > 0)
	{
		debt = debt + debt*0.05;
		if (debt % 1000 > 0)
			debt += 1000 - debt % 1000;

		
	}
	cout << debt << endl;
}

Measured memory_bytes: 1160
#include <iostream>
#include <cstdio>
#include <vector>
#include <iomanip>
using namespace std;

int main() {
    int N;
    int K;

    scanf("%d%d", &N, &K);

    std::vector <int> dices(N);
    for (int i = 0; i < N; ++i) {
        scanf("%d", &dices[i]);
    }

    int maxVal = 0; //max 2000000 * 1000
    int sum = 0;

    // expected value : (1 + .... p) / p = (1+p) * p / 2 / p = (1+p) / 2
    for (int i = 0; i < K; ++i) {
        sum += (dices[i] + 1);
    }

    maxVal = sum;

    for (int i = K; i < N; ++i) {
        sum -= (dices[i-K] + 1);
        sum += (dices[i] + 1);

        maxVal = max(maxVal, sum);
    }

    std::cout << std::setprecision(10) << maxVal / 2.0 << std::endl;
    return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;

int main(){
    size_t H, W, d;
    cin >> H >> W >> d;
    for(size_t i = 0; i < H; ++i, cout << endl)for(size_t j = 0; j < W; ++j)cout << "RGBY"[((i + i + j + j) / d & 2) + ((i + W - j) / d & 1)];
    return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <functional>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <cassert>
#include <exception>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> P;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<P> vp;
#define rep(i,a,n) for(ll i = (a);i < (n);i++)
#define per(i,a,n) for(ll i = (a);i > (n);i--)
#define lep(i,a,n) for(ll i = (a);i <= (n);i++)
#define pel(i,a,n) for(ll i = (a);i >= (n);i--)
#define clr(a,b) memset((a),(b),sizeof(a))
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define sz size()
#define print(X) cout << (X) << endl
const ll INF = 1e+9+7;
ll n,m,l;
string s,t;
ll d[200010],dp[550][550];

int main(){
  ll a[200010],b[200010],c[200010];
  cin >> n;
  rep(i,0,n-1)cin >> a[i] >> b[i] >> c[i];
  rep(i,0,n-1){
    m = 0;
    rep(j,i,n-1){
      if(m < b[j])m = b[j];
      else if(m % c[j])m += c[j] - (m % c[j]);
      m += a[j];
    }
    print(m);
  }
  puts("0");
  return 0;
}

Measured memory_bytes: 4352
#include<iostream>
#include<string>
#include<cmath>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<algorithm>

using namespace std;

int a,b;
int main(){
  cin>>a>>b;

  if(b >= a) cout<<a<<endl;
  else cout<<(a-1)<<endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <stack>
using namespace std;

int main(void){
	int omori[10]={1,2,4,8,16,32,64,128,256,512},a;
	stack<int> st; 
	int kari;
	while(cin>>a){
		for(int i=9; 0<=i; i--)
		{
			if(a-omori[i]>-1)
			{
				st.push(omori[i]);
				a=a-omori[i];
			}
		}
		while(1)
		{
			cout << st.top();
			st.pop();
			if (st.empty())break;
			else cout<<" ";
		}
		cout<<endl;
	}
	return 0;
}

Measured memory_bytes: 1200
#Python標準入出力

import numpy as np

# 1行に複数の文字列（数字）を取得，整数に直す
# In[0] = A, [1] = P
In = list(map(int, input().split()))

A = In[0]
P = In[1]

piece = 3*A + P
pie = int(piece/2)

print(pie)




Measured memory_bytes: 22124
#include "bits/stdc++.h"
#define _overload3(_1,_2,_3,name,...)name
#define _rep(i,n)repi(i,0,n)
#define repi(i,a,b)for(int i=int(a),i##_len=(b);i<i##_len;++i)
#define MSVC_UNKO(x)x
#define rep(...)MSVC_UNKO(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define all(c)c.begin(),c.end()
#define write(x)cout<<(x)<<'\n'
using namespace std; typedef long long ll; template<class T>using vv = vector<vector<T>>;
template<class T>auto vvec(int n, int m, T v) { return vv<T>(n, vector<T>(m, v)); }
template<class T, class U>bool chmax(T& a, U&& b) { return a < b ? a = b, 1 : 0; }
template<class T, class U>bool chmin(T& a, U&& b) { return b < a ? a = b, 1 : 0; }
constexpr int INF = 1 << 29, MOD = int(1e9) + 7; constexpr ll LINF = 1LL << 60;
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10); }; }aaaa;

int main() {
    int N;
    cin >> N;
    vector<int> P(N), Q(N);
    rep(i, N) cin >> P[i];
    rep(i, N) cin >> Q[i];

    vector<int> A(N);
    iota(all(A), 1);
    int a, b;
    int idx = 0;
    do {
        if (A == P) a = idx;
        if (A == Q) b = idx;
        idx++;
    } while (next_permutation(all(A)));

    write(abs(a - b));
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>    
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <cstring>
#include <cmath>
#define pb push_back
#define mk make_pair
#define eps 1e-8
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long LL;
typedef long double LD;
typedef unsigned int uii;
typedef pair<int,int> pii;
typedef pair<int, pair<int, int> >piii;
typedef unsigned long long uLL; 
typedef vector<int> vii; 
const int inf = 1e9;
const LL INF = 1e18;
const int M = 1e9 + 7;
//__int128
const int maxn = 3e5;
char s[maxn];

bool ok(int x, int y){
	for(int i = x + 1; i <= y; ++i){
		if(s[i - 1] == '#' && s[i] == '#'){
			return 0;
		}
	}
	return 1;
}

int main(int argc, char const *argv[])
{
#ifndef ONLINE_JUDGE
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0);
	int a, b, c, d, n;
	cin >> n >> a >> b >> c >> d >> (s + 1);
	if(s[c] == '#' || s[d] == '#' || !ok(b, d) || !ok(a, c)) {
		cout << "No" << endl;
		return 0;
	}
	if(c < d){
		cout << "Yes" << endl;
	} else {
		for(int i = b; i <= d; ++i){
			if(s[i] == '.' && s[i - 1] == '.' && s[i + 1] == '.'){
				cout << "Yes" << endl;
				return 0;
			}
		}
		cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
#define rep(i, n) for(i = 0; i < n; i++)
#define int long long
using namespace std;
 
int n;
int x[50], y[50];
 
signed main() {
	int i, j, k;
	
	cin >> n;
	rep(i, n) cin >> x[i] >> y[i];
	
	int ans = n;
	rep(i, n) {
		rep(j, n) {
			if (i == j) continue;
			int p = x[i] - x[j];
			int q = y[i] - y[j];
			if (p < 0 || (p == 0 && q < 0)) continue;
			
			int usedCnt = 0;
			bool used[50] = {false};
			int loopCnt = 0;
			while (usedCnt < n) {
				int id = -1;
				rep(k, n) {
					if (used[k]) continue;
					if (id == -1 || x[id] > x[k] || (x[id] == x[k] && y[id] > y[k])) {
						id = k;
					}
				}
				if (id == -1) { cout << "error" << endl; return 0; }
				
				used[id] = true; usedCnt++;
				while (true) {
					rep(k, n) {
						if (used[k]) continue;
						if (x[k] == x[id] + p && y[k] == y[id] + q) {
							break;
						}
					}
					if (k == n) break;
					used[k] = true; usedCnt++;
					id = k;
				}
				loopCnt++;
			}
			ans = min(ans, loopCnt);
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
function Main(input) {
  	input = input.split("\n");
  	var n = parseInt(input[0], 10);
  	s = input[1];
  	var l=new Array(26);
  	var r=new Array(26);
  	for (var i=0; i<26; i++){
      
      for (l[i]=0; l[i]<n; l[i]++){
          if (s.charCodeAt(l[i])==i+97){
           break; 
          }
      }
      
      for (r[i]=n; r[i]>=l[i]; r[i]+=-1){
          if (s.charCodeAt(r[i])==i+97){
           break; 
          }
       }    
    }
  var counter;
  var max=0;
  for (var j=0;j<n;j++){
    counter=0;
    for (var k=0; k<26; k++){
      if (j>=l[k] && j<r[k]){
       counter++; 
      }
    }
    if (counter>max){
     max=counter; 
    }
  }
  console.log('%d',max);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7372
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <cassert>
#include <string>
#include <cmath>
#define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define lowbit(x) (x & -x)
using namespace std;
typedef long long ll;
const int MAX = 0x7ffffff;
int t;

void slove()
{
	int n;
	cin >> n;
	bool f = false;
	while(n)
	{
		if(n % 10 == 7)f = 1;
		n = n / 10;
	}
	if(f)cout << "Yes" << endl;
	else cout << "No" << endl;
}
int main()
{
	SIS;
	slove();
}

Measured memory_bytes: 3640
q = []
loop do
  i = gets&.to_i
  break if i.nil? || i == 0
  q << i
end
max = q.max
arr = Array.new(max + 1)

(2..max).each do |i|
  next if !arr[i].nil? && !arr[i]
  arr[i] = true
  (2..(max / i).to_i).each do |j|
    idx = i * j
    break if idx > max
    arr[i * j] = false
  end
end

q.each do |que|
  p arr[1..que].select{|i| i}.size
end



Measured memory_bytes: 30308
#include<bits/stdc++.h>
using namespace std;

int main(){
  long long int k;
  cin >> k;
  int x=0;
  int ans=0;
  for(int i=1;i<=k;i++){
    x=x*10+7;
    x%=k;
    if(x==0){
      ans=i;
      break;
    }
  }
  if(ans==0){
    cout << -1 << endl;
  }else{
    cout << ans << endl;
  }
}

Measured memory_bytes: 3540
import java.util.*;
import java.lang.*;
import java.math.*;

public class Main {
	Scanner sc = new Scanner(System.in);

	class State implements Comparable<State> {
		int s;
		int x;
		int p;
		double t;
		boolean end = false;

		State(int s, int x, int p, double t) {
			this.s = s;
			this.x = x;
			this.p = p;
			this.t = t;
		}

		@Override
		public int compareTo(State arg0) {
			return this.t - arg0.t < 0 ? -1 : 1;
		}

	}

	void run() {

		for (;;) {
			int n = sc.nextInt();
			int m = sc.nextInt();
			if ((n | m) == 0) {
				break;
			}
			n++;
			int s = sc.nextInt();
			int g = sc.nextInt();

			int map[][] = new int[n][n];
			int lim[][] = new int[n][n];

			for (int i = 0; i < n; i++) {
				Arrays.fill(map[i], Integer.MAX_VALUE >> 2);
			}

			for (int i = 0; i < m; i++) {
				int x = sc.nextInt();
				int y = sc.nextInt();
				int d = sc.nextInt();
				int c = sc.nextInt();
				map[x][y] = d;
				map[y][x] = d;
				lim[x][y] = c;
				lim[y][x] = c;
			}

			double ans[][][] = new double[n][n][31];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					Arrays.fill(ans[i][j], Integer.MAX_VALUE >> 3);
				}
			}

			PriorityQueue<State> q = new PriorityQueue<State>();
			q.add(new State(1, s, 0, 0));
			ans[s][0][1] = 0;
			for (;;) {
				if (q.isEmpty()) {
					System.out.println("unreachable");
					break;
				}
				
				State now = q.poll();
				if (now.end) {
					System.out.println(now.t);
					break;
				}
				if (ans[now.x][now.p][now.s] < now.t) {
					continue;
				}
				
				for (int i = 1; i < n; i++) {

					if (i == now.p) {
						continue;
					}
					if (now.x == i) {
						continue;
					}
					if (map[now.x][i] > Integer.MAX_VALUE >> 3) {
						continue;
					}
					if (lim[now.x][i] < now.s) {
						continue;
					}
					for (int ns = now.s - 1; ns <= now.s + 1; ns++) {
						if (ns <= 0) {
							continue;
						}
						if (ns > 30) {
							continue;
						}
						if (now.s == 1 && i == g) {
							State st = new State(ns, i, now.x, now.t
									+ (double) map[now.x][i] / (double) now.s);
							st.end = true;
							q.add(st);
						}
						if (now.t + (double) map[now.x][i] / (double) now.s < ans[i][now.x][ns]) {
							ans[i][now.x][ns] = now.t + (double) map[now.x][i]
									/ (double) now.s;
							State st = new State(ns, i, now.x, now.t
									+ (double) map[now.x][i] / (double) now.s);
							if (now.s == 1 && i == g) {
								st.end = true;
							}
							q.add(st);
						}
					}
				}
			}
		}
	}

	public static void main(String[] args) {
		Main m = new Main();
		m.run();
	}
}

Measured memory_bytes: 14000
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
	
	string s; cin >> s;
	ll k; cin >> k;
	ll firstNotOne;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] != '1') {
			firstNotOne = i + 1;
			break;
		}
	}
	if (firstNotOne <= k) {
		cout << s[firstNotOne - 1] << endl;
	}
	else {
		cout << 1 << endl;
	}
	return 0;
}

Measured memory_bytes: 3628
from collections import *
from heapq import *
from itertools import *
#from fractions import gcd

from decimal import *
import copy
from bisect import *
import time
import sys
import math

input=lambda :sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**7)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))

X,Y,Z=map(int,input().split())
print(Z,X,Y)


Measured memory_bytes: 60012
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;

int n, pos;
vector<int> pre, in, post;

void rec(int l, int r) {
  if(l >= r) return;
  int root = pre[pos++];
  int m = distance(in.begin(), find(in.begin(), in.end(), root));
  rec(l, m);
  rec(m + 1, r);
  post.push_back(root);
}

void solve() {
  pos = 0;
  rec(0, pre.size());
  for(int i = 0; i < n; i++) {
    if(i) cout << " ";
    cout<<post[i];
  }

  cout<<endl;
}

int main(){
  int k;
  cin >> n;

  for(int i = 0; i < n; i++) {
    cin >> k;
    pre.push_back(k);
  }

  for(int i = 0; i < n; i++) {
    cin >> k;
    in.push_back(k);
  }

  solve();

  return 0;
}



Measured memory_bytes: 3156
#include <iostream>
using namespace std;

int a[1010101], n;

int func(int p, int r){
    int x = a[r];
    int i = p-1;
    
    for (int j = p; j < r; j++){
        
        
        if (a[j] <= x){
            i++;
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }
    
    i++;
    int temp = a[i];
    a[i] = a[r];
    a[r] = temp;
    return i;
}


int main() {
	int c;
	cin >> n;
	for (int k = 0; k < n; k++) {
		cin >> a[k];
	}
	c = func(0, n - 1);
	for (int k = 0; k < n; k++) {
		if (k) {
			cout << ' ';
		}
		if (k == c) {
			cout << '[';
		}
		cout << a[k];
		if (k == c) {
			cout << ']';
		}
	}
	cout << endl;
	return 0;
}

















Measured memory_bytes: 3456
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <iomanip>

using namespace std;

int main(){
   int N;
   int M;
   cin >> N >> M;
   int H[N];
   for(int i=0;i<N;i++){
      cin >> H[i];
   }
   bool ok[N];
   memset(ok,true,sizeof(ok));
   for(int i=0;i<M;i++){
      int a,b;
      cin >> a >> b;
      a--;
      b--;
      if(H[a]<=H[b]) ok[a]=false;
      if(H[b]<=H[a]) ok[b]=false;
   }
   int ans=0;
   for(int i=0;i<N;i++){
      if(ok[i]) ans++;
   }
   cout << ans << endl;
   return 0;
}


Measured memory_bytes: 4124
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>


using namespace std;

// vector<vector<int>> mat(N, vector<int>(M, 0));

int main(int argc, const char *argv[])
{
    //ABC138
    int N;

    cin>>N;

    vector<double> vec(N,0);
    for (int i = 0; i < N; i++)
    {
        cin>>vec[i];
    }

    sort(vec.begin(),vec.end());

    int pow_s = N - 1;
    vec[0] = vec[0] / pow(2,double(pow_s));
    for (int i = 1; i < N; i++)
    {
        vec[i] = vec[i] / pow(2, double(pow_s));

        pow_s = pow_s -1;
    }

    double ANS = 0;

    for (int i = 0; i < N; i++)
    {
        ANS += vec[i];
    }
    
    cout<<ANS;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rep2(i,s,n) for(int i = (s); i < (n); ++i)
#define ll long long
#define ld long double
#define P pair<ll,ll>
#define all(v) v.begin(),v.end()

const ll mod = 1e9+7;
const ll INF = 1e18;
const double pi = acos(-1.0);

ll f(ll n){
    ll sum=0;
    for(int i=1;i<=n;i++){
        if(n%i==0) sum++;
    }
    return sum;
}

int main(void)
{
    ll a,b,k; cin>>a>>b>>k;
    vector<ll> gcd;
    for(int i=1;i<=min(a,b);i++){
        if(a%i==0 && b%i==0) gcd.push_back(i);
    }
    reverse(all(gcd));
    cout<<gcd[k-1]<<endl;
    return 0;
}

Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 1;
const int MAXK = 1e3 + 1;

int b_cnt[MAXK*2][MAXK*2];
int w_cnt[MAXK*2][MAXK*2];
int n, k;

int RangeSum(int r0, int c0, int r1, int c1, int fack[MAXK*2][MAXK*2]) {
	return fack[r1][c1] + fack[r0-1][c0-1] - fack[r1][c0-1] - fack[r0-1][c1];
}

int main() {
	ios_base::sync_with_stdio(false);
	int x, y;
	char c;
	cin >> n >> k;
	int tot_w = 0, tot_b = 0;
	for(int i = 0; i < n; i++) {
		cin >> x >> y >> c;
		if(c == 'W') tot_w++;
		else tot_b++;
		x %= 2 * k, y %= 2 * k;
		x++, y++;
		if(c == 'B') {
			b_cnt[x][y]++;
		} else {
			w_cnt[x][y]++;
		}
	}
	for(int i = 1; i <= k*2; i++) {
		for(int j = 1; j <= k*2; j++) {
			b_cnt[i][j] += b_cnt[i-1][j] + b_cnt[i][j-1] - b_cnt[i-1][j-1];
			w_cnt[i][j] += w_cnt[i-1][j] + w_cnt[i][j-1] - w_cnt[i-1][j-1];
		}
	}
	int res = 0;
	for(int r0 = 1; r0 <= k; r0++) {
		for(int c0 = 1; c0 <= k; c0++) {
			int in_w = 0, in_b = 0;
			in_w += RangeSum(1, 1, r0, c0, w_cnt);
			in_b += RangeSum(1, 1, r0, c0, b_cnt);
			in_w += RangeSum(r0 + 1, c0 + 1, r0 + k, c0 + k, w_cnt);
			in_b += RangeSum(r0 + 1, c0 + 1, r0 + k, c0 + k, b_cnt);
			{
				int rl, cl, ru, cu;
				rl = 1, cl = c0 + k + 1, ru = r0, cu = 2*k;
				if(cl <= cu) {
					in_w += RangeSum(rl, cl, ru, cu, w_cnt);
					in_b += RangeSum(rl, cl, ru, cu, b_cnt);
				}
				rl = r0 + k + 1, cl = 1, ru = 2*k, cu = c0;
				if(rl <= ru) {
					in_w += RangeSum(rl, cl, ru, cu, w_cnt);
					in_b += RangeSum(rl, cl, ru, cu, b_cnt);
				}
				rl = r0 + k + 1, cl = c0 + k + 1, ru = 2*k, cu = 2*k;
				if(rl <= ru and cl <= cu) {
					in_w += RangeSum(rl, cl, ru, cu, w_cnt);
					in_b += RangeSum(rl, cl, ru, cu, b_cnt);
				}
			}
			int A = in_b + tot_w - in_w;
			int B = in_w + tot_b - in_b;
			res = max(res, max(A, B));
		}
	}
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 31616
h,w = map(int, input().split())

import numpy as np

f = []
for i in range(h):
    f.append(list(map(lambda x: 0 if x=='.' else 1, list(input()))))
f = np.matrix(f)

for _ in range(2):
    f = f.T
    g = []
    for i in range(f.shape[0]):
        if np.sum(f[i]) > 0:
            g.append(f[i].tolist()[0])
    f = np.matrix(g)

for i in range(len(f)):
    print("".join(list(map(lambda x:str(x), np.array(f[i]).ravel().tolist()))).replace('1','#').replace('0','.'))

Measured memory_bytes: 21360
h, w = map(int, input().split())
mat = []
for i in range(h):
  a = list(map(int, input().split()))
  mat.append(a)
for i in range(h):
  b = list(map(int, input().split()))
  for j in range(w):
    mat[i][j] = abs(mat[i][j]-b[j])
m = max(map(max, mat))
dp = [[0b0 for i in range(w)] for k in range(h)]
dp[0][0] |= 0b1 << mat[0][0]
for y in range(h):
  for x in range(w):
        if x > 0:
          dp[y][x] |= dp[y][x-1] << mat[y][x]
          dp[y][x] |= dp[y][x-1] >> mat[y][x]
          anded = dp[y][x-1] & int('1'*(mat[y][x]+1), 2)
          reverse = format(anded, "0"+str(mat[y][x]+1)+"b")[::-1]

          dp[y][x] |= int(reverse, 2)
        if y > 0:
          dp[y][x] |= dp[y-1][x] << mat[y][x]
          dp[y][x] |= dp[y-1][x] >> mat[y][x]
          anded = dp[y-1][x] & int('1'*(mat[y][x]+1), 2)
          reverse = format(anded, "0"+str(mat[y][x]+1)+"b")[::-1]

          dp[y][x] |= int(reverse, 2)
        #print(bin(dp[y][x]))

keta = 0
while dp[h-1][w-1] % 2 == 0:
  keta += 1
  dp[h-1][w-1] //= 2
print(keta)


Measured memory_bytes: 57176