akhauriyash/Code-Regression huggingface dataset:
import java.text.DecimalFormat;
import java.util.stream.LongStream;
import java.util.stream.IntStream;
import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) {
        FastScanner sc = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);

        AtCoder problem = new AtCoder(sc);
        problem.solve(out);

        out.flush();
    }

}

class AtCoder {

    final int N;
    final String S;

    AtCoder(FastScanner sc) {
        N = sc.nextInt();
        S = sc.next();
    }

    void solve(PrintWriter out) {
        int cnt = 0;
        for (int i = 0; i <= N - 3; i++) {
            if (S.substring(i, i + 3).equals("ABC")) {
                cnt++;
            }
        }
        out.println(cnt);
    }

}

// https://qiita.com/p_shiki37/items/a0f6aac33bf60f5f65e4
class FastScanner {

    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;

    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        } else {
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }

    private int readByte() {
        if (hasNextByte()) {
            return buffer[ptr++];
        } else {
            return -1;
        }
    }

    private static boolean isPrintableChar(int c) {
        return 33 <= c && c <= 126;
    }

    public boolean hasNext() {
        while (hasNextByte() && !isPrintableChar(buffer[ptr])) {
            ptr++;
        }
        return hasNextByte();
    }

    public String next() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while (isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    public long nextLong() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while (true) {
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            } else if (b == -1 || !isPrintableChar(b)) {
                return minus ? -n : n;
            } else {
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }

    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) {
            throw new NumberFormatException();
        }
        return (int) nl;
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }
}


Measured memory_bytes: 21460
#include <algorithm>
#include <bits/stdc++.h>
#include <cstdint>
#include <iostream>
#include <iterator>
#include <vector>

// lib/util.hpp
#ifndef UTIL_HPP
#define UTIL_HPP


typedef std::int_fast64_t i64;
typedef std::uint_fast64_t u64;
typedef std::int_fast32_t i32;
typedef std::uint_fast32_t u32;

namespace tools {
  template <typename T>
  void read(std::vector<T>& vector, const typename std::vector<T>::size_type size) {
    vector.reserve(size);
    std::copy_n(std::istream_iterator<T>(std::cin), size, std::back_inserter(vector));
  }

  template <typename T, std::size_t N>
  void read(std::array<T, N>& array) {
    std::copy_n(std::istream_iterator<T>(std::cin), N, array.begin());
  }
}

#endif

// main.cpp

int main() {
  i64 X, A;
  std::cin >> X >> A;
  std::cout << (X < A ? 0 : 10) << std::endl;
  return 0;
}

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

int main(){
  long long a,b,c,d;
  cin >> a >> b >> c >> d;
  long long res = a*c;
  res= max(res,a*d);
  res = max(res,b*c);
  res = max(res,b*d);
  cout << res << endl;
}


Measured memory_bytes: 3624
L = str(input());MOD = pow(10,9)+7
N = len(L) #N桁

dp = [[0]*2 for _ in range(N+1)]
#dp[i+1][j]
#i桁目で和が完全一致ならj=1
#それ以外ならj=0
dp[0][1] = 1

for i in range(N):
  if L[i] == "0":
    dp[i+1][1] = dp[i][1] #j=1で(0,0)
    dp[i+1][0] = dp[i][0]*3%MOD #j=0で何でもよい
  else:
    dp[i+1][1] = dp[i][1]*2%MOD
    dp[i+1][0] = (dp[i][1] + dp[i][0]*3)%MOD 
ans = (dp[N][0] + dp[N][1])%MOD
print(ans)

Measured memory_bytes: 85296
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		String s = sc.next();

		if (a >= 3200) {
			System.out.println(s);
		} else {
			System.out.println("red");
		}
	}
}


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

#define INF (int)1e9+7
#define rep(i,a,b) for(int i=a;i<b;++i)
#define rrep(i,a,b) for(int i=a;i>=b;--i)
#define vi vector<int>
#define vl vector<ll>
#define vii vector<vector<int>>
#define vll vector<vector<long long>>
#define pii pair<int,int>
#define pll pair<long,long>
#define vpii vector<pii>
#define vpll vector<pll>
#define N 100005
#define pb push_back
#define mp make_pair
#define PI 3.1415926535897932384626433832795



ll binPowM(ll a,ll b, ll m)
{ 
  ll ans=1;
  while(b>0)
  {
    if(b&1)ans=ans*a%m;
    a=a*a%m;
    b>>=1;
  }
return ans%m;
}
ll f(ll x,ll y,ll a)
{
  return (a&x)*(a&y);
}

int main()
{  
  
ll n,t;
cin>>n>>t;
vector<ll>a(n+1);
for(int i=1;i<=n;i++)
{
  cin>>a[i];
}
ll cur=t,dif=0;

for(int i=2;i<=n;i++)
{
     dif+=max(a[i]-cur,(ll)0);
     cur=t+a[i];
}

cout<<t+a[n]-dif<<"\n";


  return 0;

}





Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))
 
int main() {
  char a;
  cin>>a;
if (isupper(a))
   {
       cout << "A" << endl;
   }
   else
   {
       cout << "a" << endl;
   }

}

Measured memory_bytes: 3628
# -*- coding: utf-8 -*-
from operator import itemgetter

N,C = map(int, input().split())
record = []
for _ in range(N):
    s,t,c = map(int, input().split())
    record.append((s,t,c))
record.sort(key=itemgetter(1,0,2))

def can_record(k):
    slots = [(-1,-1)]*k  # (end_time, channel)

    for r in record:
        idx = -1
        t = -1
        for i in range(k):
            end_time, channel = slots[i]
            if channel==r[2]:
                if end_time<=r[0]:
                    if t<=end_time:
                        t = end_time
                        idx = i
            else:
                if end_time<r[0]:
                    if t<=end_time:
                        t = end_time
                        idx = i
        if idx==-1:
            return False
        else:
            slots[idx] = (r[1],r[2])
    return True

for k in range(1,C+1):
    if can_record(k):
        print(k)
        break


Measured memory_bytes: 26160
#include <bits/stdc++.h>
#include <boost/math/constants/constants.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>

int main(){
    using namespace std;
    using long_decimal = boost::multiprecision::cpp_dec_float_50;
    long_decimal pi = boost::math::constants::pi<long_decimal>();
    constexpr unsigned long dig = 20;
    unsigned long N, L;
    cin >> N >> L;
    vector<unsigned long> T(N);
    copy_n(istream_iterator<unsigned long>(cin), N, T.begin());
    long_decimal x{0}, y{0};
    vector<long_decimal> C(N), S(N);
    transform(T.begin(), T.end(), C.begin(), [&pi, &L](auto t){return static_cast<long_decimal>(boost::multiprecision::cos(pi * t / L));});
    transform(T.begin(), T.end(), S.begin(), [&pi, &L](auto t){return static_cast<long_decimal>(boost::multiprecision::sin(pi * t / L));});
    for(long i = 1; i < N; ++i){
        for(long j = 0; j < i; ++j){
            long t = N + 2 * (j - i);
            x += t * (C[i] * C[j] - S[i] * S[j]);
            y += t * (C[i] * S[j] + C[j] * S[i]);
        }
    }
    unsigned long t = N * (N - 1) * (N - 2) / 6;
    x /= t;
    y /= t;
    cout << x.str(dig, std::ios_base::fixed) << " " << y.str(dig, std::ios_base::fixed) << endl;
    return 0;
}

Measured memory_bytes: 896
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
M,K = map(int,input().split())
if M == 1:
    if K == 0:
        ans = [0,0,1,1]
        print(*ans)
    else:
        print(-1)
else:
    if K > 2**M - 1 :
        print(-1)
    else:
        if K == 0:
            ans = []
            for i in range(2**M):
                ans.append(i)
                ans.append(i)
            print(*ans)
        else:
            ans = deque([K])
            for i in range(2**M):
                if i == K:
                    continue
                ans.append(i)
                ans.appendleft(i)
            ans.append(K)
            print(*ans)

Measured memory_bytes: 25324
#pragma gcc optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,r,n) for(ll i=(ll)(r);i<(ll)(n);++i)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(x) x.begin(),x.end()
#define RALL(x) x.rbegin(),x.rend()
#define pb(n) push_back(n)
#define endl '\n'
#define P(x)  cout << #x << " = " << (x) << endl
#define IN(n) cin >> n
#define IN2(a,b) cin >> a >> b
#define IN3(a,b,c) cin >> a >> b >> c
#define VIN(V) for(int i = 0; i < (V).size(); i++) {cin >> (V).at(i);}
#define OUT(n) cout << n << endl
#define VOUT(V) REP(i, (V).size()) {cout << (V)[i] << endl;}
#define VOUT2(V) REP(i, (V).size()) {cout << (V)[i] << " ";} cout<<endl;
typedef long long int ll;
typedef vector<ll> vi;
typedef vector<pair<ll, ll> > vp;
typedef vector<string> vs;
typedef vector<char> vc;
typedef list<ll> lst;
typedef pair<ll, ll> P;
const long long INF = numeric_limits<ll>::max();
const long long MOD = 1000000007;
const long double PI = 3.1415926;
template <class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <class T> T &chmax(T &a, const T &b) { return a = max(a, b); }
ll n, m, k, ans, sum, cnt = 0; string s; char c; bool flg;

int main(){
  cin.tie(0);ios::sync_with_stdio(false);
  ll a,b;
  IN3(a,b,k);

  if (b-a < 2*k) {
    FOR(i,a,b+1) {
      OUT(i);
    }
  } else {
    FOR(i,0,k) OUT(a+i);
    RFOR(i,0,k) OUT(b-i);
  }
}


Measured memory_bytes: 256
S = list(input())
T = list(input())

i = 0
ans =[]

while i + len(T) <= len(S):
    n = 0
    for s, t in zip(S[i:i+len(T)], T):
        if s != t:
            n += 1
    ans.append(n)
    i += 1

print(min(ans))

Measured memory_bytes: 9116
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;

class Main {
	public static void main(String args[]) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		Solver solver = new Solver();
		solver.init();
		solver.readHead(in.readLine());
		for (; solver.hasNext();) {
			solver.readBody(in.readLine());
		}
		solver.solve();
	}
}

class Solver {
	int N;
	int cnt;

	public void init() {
		N = 0;
		cnt = 0;
	}

	public void readHead(String str) {
		String[] strArr = str.split(" ");
		N = Integer.parseInt(strArr[0]);
		// System.out.println(N);
	}

	public boolean hasNext() {
		// return cnt < N;
		return cnt < 1;
	}

	ArrayList<Integer> A;

	public void readBody(String str) {
		// System.out.println(str);
		String[] strArr = str.split(" ");
		A = new ArrayList<Integer>();
		for (String s : strArr)
			A.add(Integer.parseInt(s));
		cnt++;
	}

	public void solve() {
		A.sort(new Comparator<Integer>() {
			public int compare(Integer o1, Integer o2) {
				return Integer.valueOf(o2).compareTo(Integer.valueOf(o1));
			}
		});
		int alice = 0;
		int bob = 0;
		int i = 0;
		for (int card : A) {
			if (i % 2 == 0)
				alice += card;
			else
				bob += card;
			i++;
		}

		System.out.println(alice - bob);
	}
}


Measured memory_bytes: 21460
N=int(input())
a=list(map(int,input().split()))
a.sort()
#print(a)
l=[0]*(a[-1]+1)#l[i]にはiの数が入る
for i in range(N):
    l[a[i]]+=1
#print(l)
ans=0
if len(l)>3:
    for i in range(len(l)-2):
        if ans<l[i]+l[i+1]+l[i+2]:
            ans=l[i]+l[i+1]+l[i+2]
else:
    ans=sum(l)
print(ans)

Measured memory_bytes: 13964
n,m = map(int,input().split())

if abs(n-m)>=2:
    print(0)
elif abs(n-m) ==1:
    x =max(n,m)
    for i in range(1,min(n,m)+1):
        x = x*i**2%(10**9+7)
    print(x)
else:
    x =2
    for i in range(1,n+1):
        x = x*i**2%(10**9+7)
    print(x)

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <numeric>
#include <sstream>
#include <set>
#include <map>

using namespace std;
using ll = long long;

int main() {
	ll argN, argY;
	cin >> argN >> argY;

	argY /= 1000;
	for (ll i = 0; i <= argN; ++i) {
		for (ll j = 0; j <= argN - i; ++j) {
			ll k = argN - i - j;
			ll sum = i * 10 + j * 5 + k;
			if (sum == argY) {
				cout << i << ' ' << j << ' ' << k << endl;
				return 0;
			}
		}
	}
	cout << "-1 -1 -1" << endl;
}

Measured memory_bytes: 888
#include <stdio.h>
#include <stdlib.h>

typedef struct {
	int id;
	int dist;
	int num;
} kura_t;

int kura_num;
kura_t kura[15];

long long memo_cost[15][1<<15];
int memo_next[15][1<<15];

long long tansaku(int now,int been) {
	int i;
	long long weight;
	long long now_result,result;
	int r_next;
	been|=(1<<now);
	if(been==(1<<kura_num)-1)return 0;
	if(memo_cost[now][been]>0)return memo_cost[now][been]-1;
	weight=0;
	for(i=0;i<kura_num;i++) {
		if(been & (1<<i))weight+=kura[i].num;
	}
	weight*=20;
	result=0x1000000000000000LL;
	r_next=0;
	for(i=0;i<kura_num;i++) {
		if(!(been & (1<<i))) {
			now_result=tansaku(i,been);
			now_result+=abs(kura[now].dist-kura[i].dist)*(70+weight);
			if(now_result<result) {
				result=now_result;
				r_next=i;
			}
		}
	}
	memo_cost[now][been]=result+1;
	memo_next[now][been]=r_next+1;
	return result;
}

int main(void) {
	int i;
	long long now,min;
	int min_start;
	int been;
	scanf("%d",&kura_num);
	for(i=0;i<kura_num;i++) {
		scanf("%d%d%d",&kura[i].id,&kura[i].dist,&kura[i].num);
	}
	min=0x1000000000000000LL;
	min_start=0;
	for(i=0;i<kura_num;i++) {
		now=tansaku(i,0);
		if(now<min) {
			min=now;
			min_start=i;
		}
	}
	been=0;
	for(i=min_start;i>=0;i=memo_next[i][been]-1) {
		been|=(1<<i);
		printf("%s%d",(i==min_start)?"":" ",kura[i].id);
	}
	putchar('\n');
	return 0;
}

Measured memory_bytes: 5408
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while(true) {
            int h = scanner.nextInt();
            int w = scanner.nextInt();
            if (h == 0 && w == 0) break;
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    System.out.print('#');
                }
                System.out.print("\n");
            }
            System.out.print("\n");
        }
        scanner.close();
    }
}



Measured memory_bytes: 39564
#include <stdio.h>

int main(){
  int n, a[100], count = 0, x, i, j;

  scanf("%d" ,&n);
  for(i = 0; i < n; i++) scanf("%d" ,&a[i]);

  for(j = 0; j < n; j++){
    for(i = n - 1; i > 0; i--){
      if(a[i] < a[i - 1]){ 
	x = a[i];
	a[i] = a[i - 1];
	a[i - 1] = x;
	count++;
      }
    }
  }
  
  for(i = 0; i < n - 1; i++) printf("%d " ,a[i]);
  printf("%d\n%d\n" ,a[n - 1] ,count);

  return 0;
}

Measured memory_bytes: 600
#include <iostream>
using namespace std;
int main (){

string s;
cin >> s;
if (s=="SUN"){
    cout << "7";
}
else if (s=="MON"){
    cout << "6";
}
else if (s=="TUE"){
    cout << "5";
}
else if (s=="WED"){
    cout << "4";
}
else if (s=="THU"){
    cout << "3";
}
else if(s=="FRI"){
    cout << "2";
}
else if (s=="SAT"){
    cout << "1";
}
return 0;
}



Measured memory_bytes: 256
#include <cstdio>

const int mod = 1e9 + 7;
const int MAXN = 45, MAXS = ( 1 << 17 ) + 5;

template<typename _T>
void read( _T &x )
{
	x = 0;char s = getchar();int f = 1;
	while( s > '9' || s < '0' ){if( s == '-' ) f = -1; s = getchar();}
	while( s >= '0' && s <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar();}
	x *= f;
}

template<typename _T>
void write( _T x )
{
	if( x < 0 ){ putchar( '-' ); x = ( ~ x ) + 1; }
	if( 9 < x ){ write( x / 10 ); }
	putchar( x % 10 + '0' );
}

int f[MAXN][MAXS];
int N, X, Y, Z, st, all;

int bit( const int i ) { return 1 << i - 1; }
bool chk( const int S ) { return ( S & st ) == st; }
void add( int &x, const int v ) { x = ( x + v >= mod ? x + v - mod : x + v ); }
int insert( const int S, const int v ) { return ( S << v | bit( v ) ) & all; }

int main()
{
	read( N ), read( X ), read( Y ), read( Z );
	int up = 1 << X + Y + Z;
	all = ( bit( X + Y + Z ) << 1 ) - 1;
	st = bit( Z ) | bit( Y + Z ) | bit( X + Y + Z );
	
	f[0][0] = 1;
	for( int i = 0 ; i < N ; i ++ )
		for( int S = 0 ; S < up ; S ++ )
			if( f[i][S] && ! chk( S ) )
				for( int k = 1, T ; k <= 10 ; k ++ )
					if( ! chk( T = insert( S, k ) ) )
						add( f[i + 1][T], f[i][S] );
	int ans = 1;
	for( int i = 1 ; i <= N ; i ++ )
		ans = 10ll * ans % mod;
	for( int S = 0 ; S < up ; S ++ )
		if( ! chk( S ) )
			add( ans, mod - f[N][S] );
	write( ans ), putchar( '\n' );
	return 0;
}

Measured memory_bytes: 20112
#include <bits/stdc++.h> //C++の標準ライブラリを一行で一括でインクルードする
#include <math.h> //数学関数と数学定数を利用する
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
template<class T> void chmax(T &a,T b) { if (a<b) a=b;}
template<class T> void chmin(T &a,T b) { if (a>b) a=b;}

int main(){
  string o,e;
  cin >> o >> e;
  
  string ans;
  
  for(int i = 0; i< o.size();i++){
    ans += o[i];
    if(i < e.size()){
      ans += e[i];
    }
  }
  
  cout << ans;
  
  return 0;
}

Measured memory_bytes: 256
#include <cstdio>

int n,k,r,m[70];

int main()
{
    scanf("%d %d",&n,&k);
    for(int i=0;i<n;i++)
        scanf("%d",&m[i]);
    for(int i=0;i<n;i++)
        for(int j=i;j<n;j++)
            if(m[i]<m[j])
            {
                int tmp=m[i];
                m[i]=m[j];
                m[j]=tmp;
            }
    for(int i=0;i<k;i++)
        r+=m[i];
    printf("%d",r);
}


Measured memory_bytes: 128
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<cstdio>
#include<cstdlib>
#include<string>
#define REP(i,n) for(int i = 0; i < n; i++)
#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define p(s) cout << (s) << endl
#define p2(s,t) cout << (s) << " " << (t) << endl 
#define ALL(v) (v).begin(), (v).end()
typedef long long ll;
using namespace std;

static const ll mod  = 1e9 + 7;
static const ll inf  = 1e18;

static const int White = 0;
static const int Gray = 1;
static const int Black = 2;

void pvector(vector<int> A){
    cout << "[vector]";
    for(int i = 0; i < A.size(); i++){
        cout << A[i] << " ";
    }
    cout << endl;
}

string replace_with_str (string str, string str_from, string str_to) {
    string::size_type pos = 0;
    while (pos = str.find(str_from, pos), pos != string::npos) {
        str.replace(pos, str_from.length(), str_to);
        pos += str_to.length();
    }
    return str;
}

int main(){
    string S, T, ans;
    cin >> S >> T;
    bool can = 0;
    for(int i = 0; i < S.size(); i++){
        if(S[i] == T[0] || S[i] == '?'){
            bool same = 1;
            for(int j = 0; j < T.size(); j++){
                if(i + j >= S.size()){
                    same = false;
                    break;
                }
                if(!(S[i+j] == T[j] || S[i+j] == '?')){
                    same = false;
                    break;
                }
            }
            if(same){
                string s1 = S;
                s1.replace(i, T.size(), T);
                ans = replace_with_str(s1, "?", "a");
                can = true;
            }
        }
    }
    if(can) p(ans);
    else p("UNRESTORABLE");
}

Measured memory_bytes: 256
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int Q, doubles, lengths, dat[1000009], tmp[1000009], arrays[1000009]; string S, T;
bool compare_suffix(int i, int j) {
	if (dat[i] == dat[j]) {
		int ri = (i + doubles <= lengths ? dat[i + doubles] : -1);
		int rj = (j + doubles <= lengths ? dat[j + doubles] : -1);
		return ri < rj;
	}
	return dat[i] < dat[j];
}
void suffix_array() {
	lengths = S.size();
	for (int i = 0; i <= lengths; i++) arrays[i] = i, dat[i] = i < lengths ? S[i] : -1;
	for (doubles = 1; doubles <= lengths; doubles <<= 1) {
		sort(arrays, arrays + lengths + 1, compare_suffix);
		tmp[arrays[0]] = 0;
		for (int i = 1; i <= lengths; i++) tmp[arrays[i]] = tmp[arrays[i - 1]] + (compare_suffix(arrays[i - 1], arrays[i]) ? 1 : 0);
		for (int i = 0; i <= lengths; i++) dat[i] = tmp[i];
	}
}
int main() {
	cin >> S >> Q;
	suffix_array();
	for (int i = 0; i < Q; i++) {
		cin >> T;
		int l = 0, r = S.size() + 1; bool flag = false;
		while (r - l > 1) {
			int m = (l + r) / 2;
			string S1 = S.substr(arrays[m], T.size());
			if (S1 == T) {
				flag = true; break;
			}
			if (S1 < T) l = m;
			else r = m;
		}
		printf(flag ? "1\n" : "0\n");
	}
}

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

using namespace std;
using ll = long long;

using Field = vector<vector<int>>;
using Graph = vector<vector<int>>;
using P = pair<int, int>;

#define REP(i, n) for (int i = 0; i < (n); i++)
#define ALL(x) x.begin(), x.end()

vector<int> dx = {-1, 0, 1, 0};
vector<int> dy = {0, 1, 0, -1};


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

    int h, w; cin >> h >> w;
    vector<vector<char>> A(h, vector<char>(w));

    REP(i, h) {
        string line; cin >> line;
        REP(j, w) {
            A.at(i).at(j) = line.at(j);
        }
    }

    queue<P> que;
    Field dp(h, vector<int>(w, INT32_MAX));

    REP(i, h) REP (j, w) {
        if (A.at(i).at(j) == '#') {
            int y = i, x = j;
            dp.at(y).at(j) = 0;
            P _p = make_pair(i, j);
            que.push(_p);
        }
    }
    


    while (!que.empty()) {
        P p = que.front();
        que.pop();

        int y = p.first, x = p.second;

        REP (i, 4) {
            int ny = y + dy.at(i), nx = x + dx.at(i);
            if (ny < 0 || h <= ny || nx < 0 || w <= nx || A.at(ny).at(nx) == '#') continue;

            dp.at(ny).at(nx) = min(dp.at(ny).at(nx), dp.at(y).at(x) + 1);
            A.at(ny).at(nx) = '#';

            que.push(make_pair(ny, nx));

        }
    }

    int ans = 0;

    REP(i, h) {
        ans = max(ans, *max_element(dp.at(i).begin(), dp.at(i).end()));
    }

    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 13456
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
typedef pair<int,int> P;
struct edge{int to, id;};
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define mod 1000000007

using graph = vector<vector<ll>>;
int main(){
    ll k;
    cin >> k;
    int count = 1;
    ll hoge;
    hoge = 7 % k;
    bool huga[10000010];
    rep(i,1000010){
        huga[i] = false;
    }
    if(k % 2 == 0){
        count = -1;
    }
    else{
        while(hoge != 0 && count <= k){
            huga[hoge] = true;
            count++;
            hoge = (hoge * 10 + 7) % k;
            if(huga[hoge]){
                count = -1;
                break;
            }
        }
    }
    cout << count << endl;
}

Measured memory_bytes: 4616
a,b,k=map(int,input().split())
a_list=list(set([i for i in range(1,a+1) if not a%i]))
b_list=list(set([j for j in range(1,b+1) if not b%j]))
c=[]
for i in a_list:
    for j in b_list:
        if i==j:
            c.append(i)
c.sort(reverse=True)
print(c[k-1])

Measured memory_bytes: 3064
#include "bits/stdc++.h"
using namespace std;
using ll = int64_t;
template <typename T> using iit = istream_iterator<T>;
template <typename T> using oit = ostream_iterator<T>;
template <typename T> void write(ostream& out, T t) {
    out << t << '\n';
}
template <typename T, typename... Args>
void write(ostream& out, T t, Args... args) {
    out << t << ' ';
    write(out, args...);
}

const ll P = 1e9 + 7;
struct mod {
    int x;
    mod(int _x) : x(_x) {}
    mod operator*(const mod& rhs){ return static_cast<int>((ll(x) * ll(rhs.x))%P); }
};

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

    vector<ll> primes;
    {
        const int N = 1e3 + 1;
        vector<bool> comp(N);
        for (ll p = 2; p < N; p++)
            if (!comp[p]) {
                primes.push_back(p);
                for (ll m = p*p; m < N; m += p)
                    comp[m] = 1;
            }
        primes.shrink_to_fit();
    }

    ll n;
    cin >> n;

    mod ans(1);
    for (auto p : primes) {
        int cnt = 1;
        for (ll i = 1; i <= n; i++)
            for (ll j = i; j%p == 0; j /= p)
                cnt++;
        ans = ans * mod(cnt);
    }
    write(cout, ans.x);
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
"""



"""
import sys


def solve(N, M, cards, changes):
    changes.sort(key=lambda x: x[1])
    x = 0
    res = []
    while x < N and changes:
        b, c = changes.pop()
        x += b
        res.extend([c]*b)

    cards.extend(res)
    cards.sort()
    cards = cards[-N:]
    return sum(cards)


def main(args):
    N, M = map(int, input().split())
    cards = [int(a) for a in input().split()]
    changes = [[int(i) for i in input().split()] for _ in range(M)]
    ans = solve(N, M, cards, changes)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])


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

using namespace std;

typedef long long int ll;
typedef pair<ll, ll> pll;

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll A, B, C;
    cin >> A >> B >> C;
    ll s = A + B + C;
    ll m = std::max({A, B, C});
    if (s - m == m)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define N 100006
using namespace std;
int n,p,tmp,a[N];
inline int read()
{
	int x=0,c=getchar();while(c<48)c=getchar();
	while(c>47)x=x*10+c-48,c=getchar();return x;
}
void print(int x)
{
	if(x>9)print(x/10);putchar(x%10+48);
}
bool cmp(int a,int b)
{
	return a>b;
}
int main()
{
	scanf("%d",&n);n++;
	for(int i=2;i<=n;i++)scanf("%d",&a[i]),a[i]++;
	sort(a+2,a+n+2,cmp);a[1]=a[2];
	for(int i=1;a[i]>=i;i++)tmp=i-1;
	if((a[tmp+1]-tmp)%2==0)return puts("First"),0;
	for(int i=tmp;a[i]>tmp;i++)p=i;
	if((p-tmp)%2==0)return puts("First"),0;
	puts("Second"); 
}

Measured memory_bytes: 640
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef priority_queue<int> PQ;
template<class T>bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
//vector<vector<int> > dp;
//vector<vector<vector<int> > > vvvi;
//dp=vector<vector<int> >(N, vector<int>(M,0));
//vector<pair<int,int> > v;
//v.push_back(make_pair(x,y));
//priority_queue<int,vector<int>, greater<int> > q2;



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

	int N, M, ma = -1;
	cin >> N >> M;
	VI A(N);
	REP(i, N) {
		cin >> A[i];
		chmax(ma, A[i]);
	}
	rSORT(A);
	VI a = A;
	SORT(a);


	int L = 0, R = ma * 2, X;
	int res = 0;
	while (L <= R) {
		X = (L + R) / 2;
		int cnt = 0;
		REP(i, N) {
			int s;
			if (X - A[i] <= 0)s = N;
			else s = a.end() - LB(a, X - A[i]);
			cnt += s;
		}
		if (cnt < M) {
			R = X - 1;
		}
		else {
			chmax(res, X);
			L = X + 1;
		}
	}
	//選ぶ握手の中で最低の幸福度
	//あとはO(NlogN)でXを下回らないように握手を選んでく


	int ans = 0;
	VI sum1(N + 1, 0);
	eFOR(i, 1, N)sum1[i] = sum1[i - 1] + A[i - 1];

	int co = 0;
	REP(i, N) {
		int s;
		if (res - A[i] <= 0)s = N;
		else s = a.end() - LB(a, res - A[i]);
		co += s;
		ans += sum1[s];
		ans += A[i] * s;
	}
	ans -= (co - M)*res;
	//選び過ぎたやつを引く
	cout << ans << endl;

	return 0;
}



Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define fi first
#define se second
long long mo = 1e9 + 7;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
template<class A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}cout << "\n";}
ld PI=3.14159265358979323846;

vector<vector<ll>> id(1005, vector<ll>(1005));
vector<vector<ll>> to(1000010);

ll toId(ll i,ll j){
    if(i>j) swap(i,j);
    return id[i][j];
}
vector<ll> memo(1000010);
vector<ll> caled(1000010);
vector<ll> dp(1000010);
ll dfs(ll v){
    if(memo[v] != 0){
        if(caled[v] == 0){
            return -1;
        }else{
            return dp[v];
        }
    }
    memo[v] = 1;
    ll res = 1;
    for(auto& u:to[v]){
        ll tmp = dfs(u);
        if(tmp == -1){
            return -1;
        }
        cmax(res,tmp+1);
    }
    caled[v] = 1;
    dp[v] = res;
    return res;
}

int main(){
    ll N;
    cin >> N;
    vector<vector<ll>> A(N, vector<ll>(N-1));
    rep(i,N){
        rep(j,N-1){
            cin >> A[i][j];
            A[i][j]--;
        }
    }
    ll V = 0;
    rep(i,N){
        rep(j,N){
            if(i>j)continue;
            id[i][j] = V++;
        }
    }
    rep(i,N){
        rep(j,N-1){
            A[i][j] = toId(i, A[i][j]);
        }
        rep(j,N-2){
            to[A[i][j+1]].push_back(A[i][j]);
        }
    }
    ll ans = 0;
    rep(i,V){
        ll res = dfs(i);
        if(res == -1){
            cout << -1 << endl;
            return 0;
        }
        cmax(ans, res);
    }
    cout << ans << endl;
}

Measured memory_bytes: 81660
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 998244353;
ll n;
vector<ll>c;
vector<ll>to[10005];
vector<ll>ans;
ll x=0;
void dfs(ll v, ll p = -1){
 ans[v]=c[x];
 x++;
 for(ll i=0; i<to[v].size(); i++){
   ll u = to[v][i];
   if(u==p) continue;
   dfs(u,v);
 }
}

int main(){
  cin >> n;
  for(int i=0; i<n-1; i++){
    ll a,b;
    cin >> a >> b;
    a--; b--;
    to[a].push_back(b);
    to[b].push_back(a);
  }
  
  ll res = 0;
  c.resize(n);
  for(int i=0; i<n; i++){
    cin >> c[i];
    res+=c[i];
  }
  sort(c.begin(),c.end());
  reverse(c.begin(),c.end());
  res-=c[0];
  
  ans.resize(n);
  
  dfs(0);
  cout << res << endl;
  for(int i=0; i<n; i++) cout << ans[i] << " ";
  
  return 0;
  
}
  
  
  
  


Measured memory_bytes: 1408
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main(): 
    N = II()
    AB = []
    for _ in range(N):
        AB.append(LI())

    # Bi の小さい順（締切の早い順）にソート O(NlogN)
    AB.sort(key=lambda x: x[1])

    current_time = 0
    for i in AB:
        current_time += i[0]
        if current_time > i[1]:
            print('No')
            return
    print('Yes')


main()

Measured memory_bytes: 41212
using static System.Math;
using static System.Console;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace AtCoder
{
	class Program
	{
		static void Main(string[] args)
		{
			var n = long.Parse(ReadLine());
			var listA = new long[n];
			var listB = new long[n];

			for(var i = 0; i < n; i++)
			{
				var line = ReadLine().Split(' ').Select(value => long.Parse(value)).ToArray();
				listA[i] = line[0];
				listB[i] = line[1];
			}

			listA = listA.OrderBy(value => value).ToArray();
			listB = listB.OrderBy(value => value).ToArray();

			if(n % 2 == 1)
			{
				WriteLine(Abs(listA[(n + 1) / 2 - 1] - listB[(n + 1) / 2 - 1]) + 1);
			}
			else
			{
				double medianA = (listA[n / 2 - 1] + listA[n / 2]) / 2.0;
				double medianB = (listB[n / 2 - 1] + listB[n / 2]) / 2.0;
				WriteLine((long)(Abs(medianA - medianB) * 2) + 1);
			}
		}
	}
}


Measured memory_bytes: 36924
import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception{
		Scanner scn = new Scanner(System.in);
		int n = scn.nextInt();
		String[] s = new String[n];
      	int[] count = new int[n];
		for(int i=0; i<s.length; i++){
			s[i] = scn.next();
          	count[i] = 0;
		}
      	Arrays.sort(s);
      	int max=0;
      	for(int i=0; i<s.length; i++){
        	for(int j=i+1; j<n; j++){
            	if(s[i].equals(s[j])) count[i]++;
              	else break;
            }
         max = Math.max(max,count[i]);
         i+=count[i];
        }
      	for(int i=0; i<s.length; i++){
        	if(count[i]==max) System.out.println(s[i]);
        }
	}
}


Measured memory_bytes: 72708
#include <bits/stdc++.h>
#define forna(i,a,n) for(int i=a;i<n;i++)
typedef long long int lli;
using namespace std;

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
lli t,n,m;string s;
cin>>n;
if(n==0) cout<<1;
else cout<<0;
}

Measured memory_bytes: 3648
from collections import Counter,defaultdict,deque
from bisect import bisect_left
import sys,math,itertools,pprint,fractions,time
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

st = time.time()
n = inp()
a = []
for i in range(n):
    b = inpl()
    a.append(deque(b))
zan = n*(n-1)//2
res = 0
while True:
    res += 1
    now = zan
    s = set()
    for i in range(n):
        if i in s or a[i] == deque([]): continue
        end = True
        chk = a[i][0] - 1
        if not chk in s and a[chk][0] == i+1:
            zan -= 1
            if not zan: 
                print(res); quit()
            a[i].popleft(); a[chk].popleft()
            s.add(i); s.add(chk)
        # print(res,i,chk,a)
        nnn = time.time()
    if now == zan:
        print(-1)
        quit()
    if nnn - st > 1.7:
        print(n*(n-1)//2)
        quit()

            


Measured memory_bytes: 37688
#include<iostream>
using namespace std;
int main()
{
  int num;
  cin >> num;
  int a,b,c,result;
  a = 9; //1桁の奇数の個数
  b = 900; //3桁の奇数の個数
  c = 90000; //5桁の奇数の個数
  if(num >= 100000){
    result = a + b + c; //6桁台の処理
  } else if (num >= 10000){
    result = a + b + (num - 10000 + 1); //5桁台の処理
  } else if (num >= 1000){
    result = a + b; //4桁台の処理
  } else if (num >= 100){
    result = a + (num - 100 + 1); //3桁台の処理
  } else if (num >= 10){ //2桁台の処理
    result = a;
  } else {
    result = num; //1桁台の処理
  }
  cout << result; //結果を出力
}

Measured memory_bytes: 256
import sys
f = sys.stdin


classes = {'light fly':(00.00, 48.00),
           'fly':(48.00, 51.00),
           'bantam':(51.00, 54.00),
           'feather':(54.00,57.00),
           'light':(57.00,60.00),
           'light welter':(60.00,64.00),
           'welter':(64.00,69.00),
           'light middle':(69.00,75.00),
           'middle':(75.00,81.00),
           'light heavy':(81.00,91.00),
           'heavy':(91.00,1000.00)}

for line in f:
    weight = float(line)
    for class_name, weights in classes.items():
        if weights[0] < weight <= weights[1]:
            print(class_name)
            break

Measured memory_bytes: 6748
#include<iostream>
#include<math.h>
#include<vector>
#include<algorithm>
#include<numeric>
#include<map>
#include<queue>
#include<deque>
#include<set>
#include<cstdio>
using namespace std;
typedef long long ll;
typedef vector<int> vec;
typedef vector<vector<int>> mat;

int main(){
    int H,W,D;cin>>H>>W>>D;
    pair<int,int> p[90010];
    int a;
    for(int i=1;i<=H;i++){
        for(int j=1;j<=W;j++){
            cin>>a;
            p[a]={i,j};
        }
    }
    ll sum[90010];
    for(int i=1;i<=D;i++)
        sum[i]=0;
    for(int i=D+1;i<=H*W;i++)
        sum[i]=sum[i-D]+abs(p[i].first-p[i-D].first)+abs(p[i].second-p[i-D].second);
    
    int Q;cin>>Q;
    int L,R;
    for(int i=0;i<Q;i++){
        cin>>L>>R;
        cout<<sum[R]-sum[L]<<endl;
    }
    return 0;
}

Measured memory_bytes: 2560
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int N;

    public static void main(String[] args) {
        FastScanner sc = new FastScanner(System.in);
        N = sc.nextInt();

        System.out.println(solve());
    }

    static int solve() {
        for (int i = N; i <= 999; i++) {
            if( i % 111 == 0 ) return i;
        }
        return -1;
    }

    @SuppressWarnings("unused")
    static class FastScanner {
        private BufferedReader reader;
        private StringTokenizer tokenizer;

        FastScanner(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
            tokenizer = null;
        }

        String next() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        String nextLine() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    return reader.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken("\n");
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        long[] nextLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = nextLong();
            return a;
        }
    }
}


Measured memory_bytes: 22740
n=gets
ws=gets.split.map(&:to_i)
sum = ws.inject(:+)
ans = 1<<30
prev_s1 = 0
prev_s2 = sum

ws.each do |w|
  prev_s1 += w
  prev_s2 -= w
  if (prev_s1 - prev_s2).abs < ans
    ans = (prev_s1 - prev_s2).abs
  end
end

p ans




Measured memory_bytes: 1788
#include "bits/stdc++.h"
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
*this << "[";
for (auto it = d.b; it != d.e; ++it)
*this << ", " + 2 * (it == d.b) << *it;
ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define cool ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int  long long int
#define pb push_back
#define fe first
#define lb lower_bound 
#define ub upper_bound
#define pii pair<pair<int,int>,pair<int,int> >
#define se second
#define endl "\n"
#define pi pair<int, int>
#define mi          map<int,int>
#define mii         map<pi,int>
#define vi vector<int> 
#define vvi vector<vi>
#define bs   binary_search
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rep1(i,a,b) for(int i=a;i<=b;i++)	
#define all(c) (c).begin(),(c).end()
#define sz(x)       (int)x.size() 
#define PI 3.14159265358979323846

 const int N=2e5+5;

 int mod= 1e9+7;
 int dx[4]={0,0,+1,-1};
 int dy[4]={+1,-1,0,0};  
 
 
int po(int a, int b) {
	a %= mod;
	int res = 1;
	while (b > 0) {
		if (b & 1)
			res = (res * a) % mod;
		a =(a*a) % mod;
		b >>= 1;
	}
	 return res;	
   }
  

   
     void solve() {
	     int  n;
	     cin>>n;
	     vi v(n,0);
	     rep(i,0,n) cin>>v[i];
	     int f=0;
	     rep(i,0,n) {
			  if(v[i]%2==0) {
				    if(!(v[i]%3==0 || v[i]%5==0)) {
						  f=1;
						  break;
						}
				  }
		  }
		  
		  if(f) cout<<"DENIED\n";
		  else cout<<"APPROVED\n";
			 
	       	  		   		   
	 }

    
int32_t main() {
	cool;
	int t=1;
	//cin>>t;
	while(t--)
	solve();


return 0;	   
}


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

#define fi first
#define se second
#define FO(x, n) for (int x = 0; x < n; ++x)
#define FOR(x, a, b) for (int x = a; x < b; ++x)
#define RFO(x, n) for (int x = n - 1; x >= 0; --x)
#define RFOR(x, a, b) for (int x = b - 1; x >= a; --x)
#define FOR_ITER(x, a) for(auto x = a.begin(); x != a.end(); ++x)

using namespace std;

typedef unsigned char byte;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<string, string> pss;
typedef pair<ll, ll> pll;
inline bool feq(const double& a, const double& b) { return fabs(a - b) < 1e-10; }



int n, m;

int main(){
//    int n, l;
//    cin >> n >> k;
//    vector<bool> dislike(10, false);
//
//    FOR(i, 0, k) {
//        int t;
//        cin >> t;
//        dislike[t] = true;
//    }


    string str;
    FO(i, 3) {
        cin >> str;
        char ch = str.at(0);
        ch += ('A'-'a');
        cout << ch ;
    }


        cout<< endl;



    return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env ruby

index = 0
numbers = []

loop do
    numbers[index] = gets.chomp.to_i
    if numbers[index] != 0 then
        index += 1
    else
        break
    end
end

for i in 0...index do
    puts "Case #{i + 1}: #{numbers[i]}"
end


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

using namespace std;
#define PI 3.14159265359
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define FORN(i,a,b) for(int i=a;i<=b;i++)
#define FORRN(i,a,b) for (int i = (a); i >= (b); i--)
#define FORR(i,a,b) for (int i = (a); i > (b); i--)
const int INF = 1<<31;
typedef unsigned long long ull;
typedef long long ll;
typedef long long int LL;

ll n;

int main(){
    ios_base::sync_with_stdio(false); //Fast I/O
    cin.tie(0);
    cout.tie(0);
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);

    cin >> n;
    ll res=2*(n/11);
    n=n%11;
    
    if(n){
        res++;
        n-=6;
    }
    if(n>0){
        res++;
    }
    cout << res << endl;

    return 0;
}


Measured memory_bytes: 384
#include <stdio.h>
#include <string.h>
 
int x;
char y[101];
 
int main(){
	scanf("%d",&x);
	scanf("%s",&y);
	int len = strlen(y);
	if(len<=x){
		printf("%s\n",y);
		return 0;
	}
	else{
		for(int i=x; i<len; i++){
			y[i]='\0';
		}
		for(int i=x; i<x+3; i++){
			y[i]='.';
		}
		printf("%s\n",y);
		return 0;
	}
}

Measured memory_bytes: 1628
n = int(input())
a = list(map(int, input().split()))
a_mi = sorted([a[i] - i - 1 for i in range(n)])
if n % 2 == 0:
    ans1 = [abs(i - a_mi[int(n / 2)]) for i in a_mi]
    ans2 = [abs(i - a_mi[int(n / 2) + 1]) for i in a_mi]
    print(min(sum(ans1), sum(ans2)))
else:
    print(sum([abs(i - a_mi[int((n - 1) / 2)]) for i in a_mi]))


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

#define rep(i,n) for(int i=0;i<(n);i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(),(a).end()

typedef long long ll;

const ll MOD=1000000007ll;
const int MAX=5100000;

using namespace std;

int inputValue(){
    int a;
    cin >> a;
    return a;
};

void inputArray(int * p, int a){
    for(int i=0;i<a;i++){
        cin >> p[i];
    }
};

void inputVector(vector<int> * p, int a){
    for(int i=0;i<a;i++){
        int input;
        cin >> input;
        p -> push_back(input);
    }
}

ll fact[MAX], fact_inv[MAX];

ll power(ll a, ll b){
	ll res=1;
	while(b>0){
		if(b&1) res=res*a%MOD;
		a=a*a%MOD;
		b>>=1;
	}
	return res;
}

// nCr
ll comb(ll n, ll r){
	ll t=1000000;
	fact[0]=1;
	    for(int i=0;i<t;i++){ fact[i+1]=fact[i]*(i+1)%MOD;}
	fact_inv[t]=power(fact[t], MOD-2);
	for(int i=0;i<t;i++){ fact_inv[i]=fact_inv[i+1]*(i+1)%MOD;}
	return (fact[n]*fact_inv[r])%MOD*fact_inv[n-r]%MOD;
}
  
int main()
{
	cin.tie(0);	ios::sync_with_stdio(false);

  int L,R,d,i; cin >> L >> R >> d;
  int ans = 0;
  for(i=L;i<=R;i++){if(i%d==0){ans++;}}
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<ll>::iterator sit;
typedef map<ll,ll>::iterator mit;

int a[111111];
map<int,int> ma;

int get(int x)
{
	if(ma.find(x)==ma.end()) return 0;
	else return ma[x];
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin>>n;
	
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		ma[a[i]]++;
	}
	
	int ans = 0;
	for(auto it = ma.begin(); it!=ma.end(); it++)
	{
		for(int i=-2;i<=2;i++)
		{
			ans = max(ans, get(it->fi+i)+get(it->fi+i+1)+get(it->fi+i+2));
		}
	}
	cout<<ans<<'\n';
}


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

using namespace std;
using ll =long long;
typedef pair<int,int> P;
#define SORT(a) sort((a).begin(),(a).end())
#define rSORT(a) reverse((a).begin(),(a).end())
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define debug(x)  cerr << #x << " = " << (x) << endl;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
//Write From this Line

int main()
{
	int n;
	cin >> n;
	vector<int> a(n);
	rep(i, n)cin>>a[i];
	
	int ans = 0;
	For(i,1,n){
		if(a[i] == a[i-1]){
			a[i] = -1;
			ans ++;
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 256