akhauriyash/Code-Regression huggingface dataset:
//header{{{
#include<bits/stdc++.h>
  
using namespace std;
 
#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define setout(n,x) setw(n+1) << setfill(x)
#define Fixed fixed << setprecision(10)
#define int int64_t
using pii = pair<int,int>;
constexpr int INF  = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int mod = 1e9+7; 
constexpr int MOD = 998244353;

template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }

template <class T> using min_heap = priority_queue<T,vector<T>,greater<T> >;
template <class T> using max_heap = priority_queue<T>;
template <class A, class B> using umap = unordered_map<A,B>;
  
int gcd(int a,int b){ return b ? gcd(b,a % b) : a;}
int lcm(int a,int b){ return a / gcd(a,b) * b;}

constexpr int dx[] = {1,0,-1,0,1,1,-1,-1};
constexpr int dy[] = {0,-1,0,1,1,-1,-1,1};
//}}}

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

    char c;
    cin >> c;
    cout << char(c + 1) << '\n';


    return 0;
}


Measured memory_bytes: 764
X, N = map(int, input().split())
P = list(map(int, input().split()))

P.sort()
ans = 10000000
for i in range(-101, 102):
  if not i in P:
    ans = min(ans, abs(i-X))

if not X-ans in P:
  print(X-ans)
else:
  print(X+ans)


Measured memory_bytes: 61916
#include <bits/stdc++.h>
using namespace std;
int main(){
    string A, B, C;
    cin >> A >> B >> C;
    char tmp = 'a';
    char ans;
    while (A.size() * B.size() * C.size() >= 0){
        if (tmp == 'a'){
            if (A.size() == 0){
                ans = 'A';
                break;
            }
            tmp = A[0];
            A.erase(A.begin());
        }else if(tmp == 'b'){
            if (B.size() == 0){
                ans = 'B';
                break;
            }
            tmp = B[0];
            B.erase(B.begin());
        }else{
            if (C.size() == 0){
                ans ='C';
                break;
            }
            tmp = C[0];
            C.erase(C.begin());
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int printBoard(int x, int y){
	int board[2] = {'#', '.'}, flip;
	for(int i = 0; i < x; i++){
		flip = i % 2;
		for(int j = 0; j < y; j++){
			printf("%c", board[flip]);
			flip = flip * (-1) + 1;
		}
		printf("\n");
	}
	
	if(x != 0 && y != 0)
		printf("\n");
		
	return 0;
}

int main(){
	int count = 0, h, w;
	do{
		scanf("%d %d", &h, &w);
		printBoard(h, w);
	}
	while(h != 0 && w != 0);
		
	return 0;
}


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

int main() 
{
	int n,k;
	cin>>n>>k;
	int a[n];
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	int dp[n];
	for(int i=0;i<n;i++)
	{
		dp[i]=INT_MAX;
	}
	dp[0]=0;
	
	
	for(int i=0;i<n;i++)
	{
		
		for(int j=1;j<=k;j++)
		{
			if((i+j)<n)
			{
				dp[i+j]=min(dp[i+j],dp[i]+abs(a[i]-a[i+j]));
		
			}
		}
		//cout<<dp[i]<<" ";
	}
	cout<<dp[n-1];

}

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

const int MOD = (int)1e9+7;
long long gcd(long long a,long long b){
	if(b==0)	return a;
	return gcd(b,a%b);
}

int main(){
	long long A,B,C,D;
	cin >> A >> B >> C >> D;

	long long ans=0;
	long long di=C*D/gcd(C,D);
	
	ans+=B/C+B/D-B/di;
	ans-=(A-1)/C+(A-1)/D-(A-1)/di;
	cout << B-A+1-ans << endl;

	return 0;
}


Measured memory_bytes: 256
from collections import deque

H, W = map(int, input().split())

mazo = [list(input()) for _ in range(H)]

cnt = 0 #初期状態の黒の数を数える
for i in range(H):
    for j in range(W):
        if mazo[i][j] == "#":
            cnt += 1

d = deque()
d.append((0,0))

move = [(-1, 0), (1, 0), (0, -1), (0, 1)]

visited = [[0]*W for _ in range(H)]

flg = False
while d:
    y, x = d.popleft()
    if (y==H-1) and (x==W-1):
        flg = True
        break

    for u, v in move:
        t = y + u
        s = x + v
        if 0 <= t and t<H and 0<=s and s<W and mazo[t][s]=="." and visited[t][s]==0:
            visited[t][s] = visited[y][x] + 1
            d.append((t, s))

if flg:
    print(H*W - cnt - visited[H-1][W-1] -1)
else:
    print(-1)


Measured memory_bytes: 9520
#include<bits/stdc++.h>
#include<cstring>
#include<cmath>
#include<iterator>
#include<cstdlib>
#define IOS   ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ses   "\n"
#define whp   " "
#define mxi 99999

#define mp make_pair
#define PII pair<int, int>
#define pf printf
#define sf scanf
#define ALL(x) x.begin(),x.end()
#define pb push_back
#define PI acos(-1)
#define sz(a) long long(a.size())
#define ff first
#define ss second
#define forch(it,s) for(auto it:s)
#define each(it,s) for(auto it = s.begin(); it != s.end(); ++it)

#define rep0(i,a,b) for(int i=a; i<b; i++)
#define rep1(i,a,b) for(int i=a; i<=b; i++)
#define rep0in(i,a,b) for(int i=a-1; i>=b; i--)
#define rep1in(i,a,b) for(int i=a; i>b; i--)
#define repv(i,a) for(auto i=a.begin(); i!=a.end();++i)

#define MS(a,b) memset(a,b,sizeof(a));

typedef long long ll;
typedef unsigned long long ull;
using namespace std;
ll fx[4]= {1,-1,0,0};
ll fy[4]= {0,0,1,-1};

typedef vector<ll> vll;
typedef vector<string> vss;
typedef vector<pair<ll,ll > > vpr;
typedef vector<pair<string,ll > > vspr;
typedef list<ll> li;
typedef list<string> ls;
typedef list<pair<ll,ll> > lpr;
typedef list<pair<string,ll> > lspr;

bool rs(ll a, ll b){return(a>b);}
ll spd(ll n){ if(n%2==0)return 2; for(ll i=3; i*i<=n; i++){if(n%i==0)return i;}return n;}

int main(){
map<ll,ll>m;
ll n; cin>>n;
ll x=1, y=1,z=1;
ll a[n+1];
MS(a,0);
ll sol;

      for(x=1; x*x<n; x++){
        for(y=1; y*y<n; y++){
            for(z=1; z*z<n; z++){
                sol=x*x+y*y+z*z+x*y+x*z+y*z;
                if(sol<=n ){
                   m[sol]++;

                    }
                }
            }
        }
        for(auto i:m){
            a[i.first]=i.second;
        }
        for(ll i=1; i<=n; i++){
            cout<<a[i]<<endl;
        }

return 0;
}


Measured memory_bytes: 4220
#include<bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
#define int long long
using namespace std;
int n,w,z,a[2001];
main(){
	cin >> n >> z >> w;

	r(i,n) cin >> a[i];
  if(n!=1)cout<<max(abs(a[n-2]-a[n-1]),abs(a[n-1]-w))<<endl;
  else cout<<abs(a[n-1]-w)<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <list>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
typedef long long lli;
typedef vector<lli> vll;
typedef vector<bool> vbl;
typedef vector<vector<lli> > mat;
typedef vector<vector<bool> > matb;
typedef vector<string> vst;
typedef pair<lli,lli> pll;
typedef pair<double,double> pdd;

lli v,e,r;
mat g;
mat d;
lli x,y,c;
priority_queue<pll,vector<pll>,greater<pll> > pq;
vbl vis;
vll ans;

int main(){
    cin >> v >> e >> r;
    g = d = mat(v);
    for(lli i = 0;i < e;i++){
        cin >> x >> y >> c;
        g[x].push_back(y);
        d[x].push_back(c);
    }
    pq.push(pll(0,r));
    vis = vbl(v);
    ans = vll(v,-1);
    while(!pq.empty()){
        x = pq.top().second;
        c = pq.top().first;
        pq.pop();
        if(vis[x]) continue;
        vis[x] = true;
        ans[x] = c;
        for(lli i = 0;i < g[x].size();i++){
            pq.push(pll(c+d[x][i],g[x][i]));
        }
    }
    for(lli i = 0;i < v;i++){
        if(ans[i] >= 0) cout << ans[i] << endl;
        else cout << "INF" << endl;
    }
    return 0;
}

Measured memory_bytes: 25316
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
typedef long long lint;
const int N=101;
int qa,qb,qr[11][11],mp[N+1][N+1];

namespace utils{
	template <class T> inline void apn(T &x,const T y){x=x<y?x:y;}
	template <class T> inline void apx(T &x,const T y){x=x>y?x:y;}
	inline int nxi(){
		int x=0;
		char c;
		while(((c=getchar())>'9'||c<'0')&&c!='-');
		const bool f=c=='-'&&(c=getchar());
		while(x=x*10-48+c,(c=getchar())>='0'&&c<='9');
		return f?-x:x;
	}
}
using namespace utils;

bool jdg(){
	for(int i=1; i<=qa; ++i){
		for(int j=1; j<=qb; ++j){
			int res=1e9;
			for(int k=1; k<=N; ++k){
				for(int l=1; l<=N; ++l){
					apn(res,(k-1)*i+(N-l)*j+mp[k][l]);
				}
			}
			assert(res>=qr[i][j]);
			if(res>qr[i][j]) return 0;
		}
	}
	return 1;
}

int main(){
	qa=nxi(),qb=nxi();
	for(int i=1; i<=qa; ++i){
		for(int j=1; j<=qb; ++j){
			const int v=qr[i][j]=nxi();
			for(int k=1; k<=N; ++k){
				for(int l=1; l<=N; ++l){
					apx(mp[k][l],v-i*(k-1)-j*(N-l));
				}
			}
		}
	}
	if(!jdg()){
		puts("Impossible");
		return 0;
	}
	puts("Possible");
	printf("%d %d\n",N<<1,N*N+2*(N-1));
	for(int i=1; i<N; ++i){
		printf("%d %d X\n",i,i+1);
		printf("%d %d Y\n",i+N,i+N+1);
	}
	for(int i=1; i<=N; ++i){
		for(int j=1; j<=N; ++j){
			printf("%d %d %d\n",i,j+N,mp[i][j]);
		}
	}
	printf("%d %d\n",1,N*2);
	return 0;
}


Measured memory_bytes: 384
package main

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

const (
	mod = int64(1000003)
)

func pow(x, y int64) int64 {
	if y == 0 {
		return 1
	}
	if y == 1 {
		return x
	}
	if y%2 == 0 {
		x2 := x * x % mod
		return pow(x2, y/2) % mod
	}
	return x * pow(x, y-1) % mod
}

func divide(x, y int64) int64 {
	return x * pow(y, mod-2) % mod
}

func main() {
	var q int
	fmt.Scan(&q)

	factorial := make([]int64, mod)
	factorial[0] = 1
	for i := int64(1); i < mod; i++ {
		factorial[i] = factorial[i-1] * i % mod
	}

	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)

	for i := 0; i < q; i++ {
		scanner.Scan()
		xi, _ := strconv.Atoi(scanner.Text())
		x := int64(xi)
		scanner.Scan()
		di, _ := strconv.Atoi(scanner.Text())
		d := int64(di)
		scanner.Scan()
		ni, _ := strconv.Atoi(scanner.Text())
		n := int64(ni)

		if x == 0 {
			fmt.Println(0)
			continue
		}
		if d == 0 {
			fmt.Println(pow(x, n))
			continue
		}

		xdd := divide(x, d) % mod
		if xdd+n-1 >= mod {
			fmt.Println(0)
			continue
		}
		ret := divide(factorial[xdd+n-1], factorial[xdd-1]) % mod
		ret = ret * pow(d, n) % mod
		fmt.Println(ret)
	}
}


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

#define rep(i, n) for(int i = 0; i < (n); ++i)
#define repr(i, n) for(int i = (n-1); i >= 0; --i)

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; }

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

const int MAX = 200005;
const int INF = 1001001001;
const int MOD = 1000000007;

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

    string ans;
    if (a <= 0 && 0 <= b) {
        ans = "Zero";
    } else if (0 < a) {
        ans = "Positive";
    } else {
        if ((b - a) % 2) {
            ans = "Positive";
        } else {
            ans = "Negative";
        }
    }

    cout << ans << endl;   
}

Measured memory_bytes: 256
import sys
from math import sqrt
def input():
	return sys.stdin.readline()[:-1]

import heapq
class DijkstraMatrix():
	#隣接行列版
	#同一頂点の複数回探索を防ぐため訪問した頂点数を変数cntで持つ
	def __init__(self, matrix, start):
		self.matrix = matrix
		self.start = start
		self.size = len(matrix)

	def solve(self):
		self.dist = [float("inf") for _ in range(self.size)]
		self.dist[self.start] = 0
		self.prev = [-1 for _ in range(self.size)]
		self.q = []
		self.cnt = 0

		heapq.heappush(self.q, (0, self.start))

		while self.q and self.cnt < self.size:
			u_dist, u = heapq.heappop(self.q)
			if self.dist[u] < u_dist:
				continue
				#これいる？
			for v in range(self.size):
				w = self.matrix[u][v]
				if self.dist[v] > u_dist + w:
					self.dist[v] = u_dist + w
					self.prev[v] = u
					heapq.heappush(self.q, (self.dist[v], v))

			self.cnt += 1

		return

	def distance(self, goal):
		return self.dist[goal]

	def path(self, goal):
		self.path = [goal]
		while self.path[-1] != self.start:
			self.path.append(self.prev[self.path[-1]])
		return self.path[::-1]

xs, ys, xt, yt = map(int, input().split())
n = int(input())
b = [[xs, ys, 0], [xt, yt, 0]] + [list(map(int, input().split())) for _ in range(n)]
d = [[float("inf") for _ in range(n+2)] for _ in range(n+2)]

for i in range(n+2):
	for j in range(n+2):
		if i != j:
			d[i][j] = max(sqrt((b[i][0] - b[j][0])**2 + (b[i][1] - b[j][1])**2) - b[i][2] - b[j][2], 0)

dijkstra = DijkstraMatrix(d, 0)
dijkstra.solve()
print(dijkstra.distance(1))

Measured memory_bytes: 101852
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>

using namespace std;

int main() {
	int n;
	cin >> n;
	int ans = 1000 - n % 1000;
	if (ans == 1000) ans = 0;
	std::cout << ans << endl;

	return 0;
}

Measured memory_bytes: 3156
#include<iostream>
#include<algorithm>
#include<math.h>
#include<queue>
#include<vector>
#include<climits>
#include<map>
#include<string>
#include<functional>
#include<iomanip>
#include<deque>
#include<random>
#include<set>
#include<bitset>
#include<cassert>

using namespace std;
typedef long long ll;
typedef double lldo;
#define mp make_pair
#define pub push_back
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
#define chmax(x,y) x = max(x,y)
ll gcd(ll a, ll b) { if (a % b == 0) { return b; } else  return gcd(b, a % b); }
ll lcm(ll a, ll b) { if (a == 0) { return b; }return a / gcd(a, b) * b; }
template<class T>ll LBI(vector<T>& ar, T in) { return lower_bound(ar.begin(), ar.end(), in) - ar.begin(); }
template<class T>ll UBI(vector<T>& ar, T in) { return upper_bound(ar.begin(), ar.end(), in) - ar.begin(); }

ll n, a[1000005] = {}, num[1000005] = {};

struct cww { cww() { ios::sync_with_stdio(false); cin.tie(0); } }star;
#include <vector>
std::vector<int> Eratosthenes(const int N)
{
	std::vector<bool> is_prime(N + 1);
	for (int i = 0; i <= N; i++)
	{
		is_prime[i] = true;
	}
	std::vector<int> P;
	for (int i = 2; i <= N; i++)
	{
		if (is_prime[i])
		{
			for (int j = 2 * i; j <= N; j += i)
			{
				is_prime[j] = false;
			}
			P.emplace_back(i);
		}
	}
	return P;
}
int main()
{
	cin >> n;
	rep(i, n)cin >> a[i];
	ll g = a[0];
	bool pc = true, flag = false, sc = false;
	rep(i, n - 1) {
		g = gcd(g, a[i + 1]);
		if (g == 1) {
			sc = true;
			break;
		}
	}
	for (const auto& x : Eratosthenes(1000000))
	{
		if (x <= 1000) {
			ll cnt = 0;
			rep(i, n) {
				if (a[i] % x == 0)cnt++;
				while (a[i] % x == 0)a[i] /= x;
				if (cnt >= 2)
					pc = false;
			}
		}
		else {
			if (!flag) {
				rep(i, n)num[a[i]]++;
				flag = true;
			}
			if (num[x] >= 2)
				pc = false;
		}
	}
	if (pc) {
		cout << "pairwise coprime" << endl;
	}
	else if (sc) {
		cout << "setwise coprime" << endl;
	}
	else {
		cout << "not coprime" << endl;
	}
	return 0;
}

Measured memory_bytes: 19524
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define INF 0x6fffffff
#define INFL 0x6fffffffffffffffLL

int main() {
	ll		a,b,c,h,i,j,k,l,m,n,x,y;
	ll		ans = 0;
	string	s;
	cin >> k >> x;
	for(i=x-k+1;i<x+k;i++) {
		if (i<-1000000) i= -1000000;
		if (i>1000000) break;
		cout << i << " ";
	}
	cout << endl;
	
	return 0;
}


Measured memory_bytes: 3628
// clang-format off
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
#define rep(i,n) for(ll i=0, i##_len=(n); i<i##_len; ++i)
#define rep1(i,n) for(ll i=1, i##_len=(n); i<=i##_len; ++i)
#define rrep(i,n) for(ll i=n-1; i>=0; --i)
#define rrep1(i,n) for(ll i=n; i>0; --i)
#define all(x) (x).begin(),(x).end()
#define SORT(x) sort(all(x))
#define SORT_DESC(x) sort((x).rbegin(),(x).rend())
#define pb push_back
#define mp make_pair
#define coutl cout<<fixed<<setprecision(10)
#define ANS(ans) cout<<ans<<endl
#define END(ans) ANS(ans); return
const ll LINF = (1LL << 62) - 1;
const int INF = (1 << 30) - 1;
template<class T>inline bool chmax(T &a, const T &b){if (a<b){a=b;return 1;}return 0;}
template<class T>inline bool chmin(T &a, const T &b){if (b<a){a=b;return 1;}return 0;}
// clang-format on

void solve(std::string s, std::string t) {
  vector<vector<ll>> dp(s.size() + 1, vector<ll>(t.size() + 1));
  ll n = s.size(), m = t.size();
  rep(i, n) rep(j, m) {
    if (s[i] == t[j]) {
      chmax(dp[i + 1][j + 1], dp[i][j] + 1);
    }
    chmax(dp[i + 1][j + 1], dp[i + 1][j]);
    chmax(dp[i + 1][j + 1], dp[i][j + 1]);
  }

  string ans = "";
  while (n > 0 && m > 0) {
    if (dp[n][m] == dp[n - 1][m])
      --n;
    else if (dp[n][m] == dp[n][m - 1])
      --m;
    else {
      ans = s[n - 1] + ans;  // == t[m-1]
      --n;
      --m;
    }
  }
  ANS(ans);
}

// clang-format off
int main() {
  std::string s;
  std::cin >> s;
  std::string t;
  std::cin >> t;
  solve(s, t);
  return 0;
}


Measured memory_bytes: 70912
import java.util.*;
import java.io.*;

public class Main{

	public static void main(String[] args) throws IOException {
		int N = readInt(), T = readInt();
		int min = Integer.MAX_VALUE;
		for(int i = 1; i<=N; i++) {
			int c = readInt(), t = readInt();
			if(t <= T) min  = Math.min(min, c);
		}
		println(min == Integer.MAX_VALUE ? "TLE" : min);
		exit();
	}

	final private static int BUFFER_SIZE = 1 << 16;
	private static DataInputStream din = new DataInputStream(System.in);
	private static byte[] buffer = new byte[BUFFER_SIZE];
	private static int bufferPointer = 0, bytesRead = 0;
	static PrintWriter pr = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

	public static String readLine() throws IOException {
		byte[] buf = new byte[64]; // line length
		int cnt = 0, c;
		while ((c = Read()) != -1) {
			if (c == '\n')
				break;
			buf[cnt++] = (byte) c;
		}
		return new String(buf, 0, cnt);
	}

	public static String read() throws IOException {
		byte[] ret = new byte[1024];
		int idx = 0;
		byte c = Read();
		while (c <= ' ') {
			c = Read();
		}
		do {
			ret[idx++] = c;
			c = Read();
		} while (c != -1 && c != ' ' && c != '\n' && c != '\r');
		return new String(ret, 0, idx);
	}

	public static int readInt() throws IOException {
		int ret = 0;
		byte c = Read();
		while (c <= ' ')
			c = Read();
		boolean neg = (c == '-');
		if (neg)
			c = Read();
		do {
			ret = ret * 10 + c - '0';
		} while ((c = Read()) >= '0' && c <= '9');

		if (neg)
			return -ret;
		return ret;
	}

	public static long readLong() throws IOException {
		long ret = 0;
		byte c = Read();
		while (c <= ' ')
			c = Read();
		boolean neg = (c == '-');
		if (neg)
			c = Read();
		do {
			ret = ret * 10 + c - '0';
		} while ((c = Read()) >= '0' && c <= '9');
		if (neg)
			return -ret;
		return ret;
	}

	public static double readDouble() throws IOException {
		double ret = 0, div = 1;
		byte c = Read();
		while (c <= ' ')
			c = Read();
		boolean neg = (c == '-');
		if (neg)
			c = Read();

		do {
			ret = ret * 10 + c - '0';
		} while ((c = Read()) >= '0' && c <= '9');

		if (c == '.') {
			while ((c = Read()) >= '0' && c <= '9') {
				ret += (c - '0') / (div *= 10);
			}
		}

		if (neg)
			return -ret;
		return ret;
	}

	private static void fillBuffer() throws IOException {
		bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
		if (bytesRead == -1)
			buffer[0] = -1;
	}

	private static byte Read() throws IOException {
		if (bufferPointer == bytesRead)
			fillBuffer();
		return buffer[bufferPointer++];
	}

	static void print(Object o) {
		pr.print(o);
	}

	static void println(Object o) {
		pr.println(o);
	}

	static void flush() {
		pr.flush();
	}

	static void println() {
		pr.println();
	}

	static void exit() throws IOException {
		din.close();
		pr.close();
		System.exit(0);
	}
}


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

#define rng(i, a, b) for (int i = int(a); i < int(b); i++)
#define rep(i, b) rng(i, 0, b)
#define gnr(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define per(i, b) gnr(i, 0, b)

using namespace std;

using ll = long long;
using P = pair<int, int>;

const int ContestCount = 26;
int d;
vector<int> c;
vector<vector<int>> s;
vector<int> last;

int calcMinus(int dd) {
  dd++;
  int res = 0;
  rep(i, ContestCount) {
    res += c.at(i) * (dd - last.at(i));
  }
  return res;
}

int main() {
  // 入力処理
  cin >> d;
  c.resize(ContestCount);
  rep(i, ContestCount) cin >> c.at(i);
  s.resize(d, vector<int>(ContestCount));
  rep(i, d) {
    rep(j, ContestCount) {
      cin >> s.at(i).at(j);
    }
  }
  // B問題用の入力
  vector<int> t(d);
  rep(i, d) {
    cin >> t.at(i);
    t.at(i)--;
  }

  last = vector<int>(ContestCount, 0);

  vector<int> v(d, 0);
  rep(dd, d) {
    // 前処理
    int score;
    if (dd == 0) {
      score = 0;
    } else {
      score = v.at(dd - 1);
    }
    // コンテスト開催
    int contest = t.at(dd);
    int plus = s.at(dd).at(contest);
    score += plus;
    last.at(contest) = dd + 1;
    // マイナス分の計算
    int minus = calcMinus(dd);
    score -= minus;
    v.at(dd) = score;
  }
  rep(i, d) {
    cout << v.at(i) << endl;
  }
  return 0;
}


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

#define rep(i,a,b)      for(int i=a;i<=b;i++)
#define revp(i,a,b)     for(int i=b;i>=a;i--)

int a,b,c;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
   
    cin>>a>>b>>c;
    if(c>=a and c<=b)
        cout<<"Yes";
    else
        cout<<"No";
}




Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

typedef long long ll;

int n,k;
int main(){
    

    scanf("%d %d",&n,&k);
    ll ans=k;

    for(int i=1;i<n;i++){
        ans*=(k-1);
    }

    printf("%lld\n",ans);
    // getchar();
    // getchar();

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define scan int n;cin>>n;for(int i=0;i<n;i++)
#define ll long long
#define vl vector<long long>
using namespace std;
int main(){
    ios_base::sync_with_stdio(false);
    int n;
    cin >> n;
    string str;
    cin >> str;
    if(n % 2 == 1) {
        cout << "No" << endl;
    }else{
        bool is=true;
        for(int i=0;i<n/2;i++){
            if(str[i] != str[n/2 + i]) {
                is = false;
                break;
            }
        }
        if(is) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define lli long long int
int main(){
	lli n;
	cin>>n;
	double p[n+1];
	for(lli i=1;i<=n;i++)
	cin>>p[i];
	double dp[n+1][n+1];
	for(lli i=0;i<=n;i++){
		for(lli j=0;j<=n;j++){
			dp[i][j]=0;
		}
	}
	dp[1][0]=1-p[1];
	dp[1][1]=p[1];
	//cout<<dp[1][1]<<"\n";
	for(lli i=2;i<=n;i++){
		for(lli j=0;j<=i;j++){
			dp[i][j]=(j-1>=0?dp[i-1][j-1]:0)*p[i]+dp[i-1][j]*(1-p[i]);
			//cout<<dp[i][j]<<" ";
		}
		//cout<<"\n";
	}
	double ans=0;
	for(lli i=n/2+1;i<=n;i++){
		ans+=dp[n][i];
	}
	cout<<setprecision(15)<<fixed<<ans;
	return 0;
}


Measured memory_bytes: 70528
# include <iostream>
# include <algorithm>
#include <array>
# include <cassert>
#include <cctype>
#include <climits>
#include <numeric>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <tuple>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <bitset>
# include <complex>
# include <chrono>
# include <random>
# include <limits.h>
# include <unordered_map>
# include <unordered_set>
# include <deque>
# include <cstdio>
# include <cstring>
#include <stdio.h>
#include<time.h>
#include <stdlib.h>
#include <cstdint>
#include <cfenv>
#include<fstream>
//#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
long long MOD = 1000000000 + 7;// ;//1000000000 + 7 998244353 924844033 1000000000 + 9;
constexpr long long INF = numeric_limits<LL>::max();
constexpr long long DINF = 1000000000000;
const double PI = acos(-1);
#define fir first
#define sec second
#define thi third
#define debug(x) cerr<<#x<<": "<<x<<'\n'
typedef pair<LL, LL> Pll;
typedef pair<double, double> Dll;
typedef pair<LL, pair<LL, LL>> Ppll;
typedef pair<LL, pair<LL, bitset<100001>>> Pbll;
typedef pair<LL, pair<LL, vector<LL>>> Pvll;
typedef pair<LL, LL> Vec2;
struct Tll { LL first, second, third; };
struct Fll { LL first, second, third, fourth; };
typedef pair<LL, Tll> Ptll;
#define rep(i,rept) for(LL i=0;i<rept;i++)
#define Rrep(i,mf) for(LL i=mf-1;i>=0;i--)
void YN(bool f) {
	if (f)
		cout << "YES" << endl;
	else
		cout << "NO" << endl;
}
void yn(bool f) {
	if (f)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
}
struct Edge { LL to, cost; };
struct edge {
	LL from, to, cost;
};
vector<vector<Edge>>g;
vector<edge>ed;
vector<Pll>pv;
map<LL, LL>ma;
set<LL>st;
int di[4][2] = { { 0,1 },{ 1,0 },{ 0,-1 },{ -1,0 } };
LL n, m, k, p, q, w, h, ans, cnt, sum,a[310000], b[310000];
string str;
bool f;
char c[1100][1100];
int main() {
	cin >> n >> m >> k;
	LL cur = k;
	rep(i, 10) {
		cur = n * cur - m;
		cout << cur << endl;
	}
	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 repp(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define repm(i,n) for(int (i)=(n-1);(i)>=0;(i)--)
#define INF (1ll<<60)
#define all(x) (x).begin(),(x).end()
typedef long long lint;
const lint MOD =1000000007;
const lint MAX = 1000000;
using Graph =vector<vector<lint>>;
typedef pair<lint,lint> P;
 
 
lint fac[MAX], finv[MAX], inv[MAX];
 
void COMinit() 
{
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (lint i = 2; i < MAX; i++)
    {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
 
long long COM(lint n, lint k)
{
    if (n < k)
        return 0;
    if (n < 0 || k < 0)
        return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
 
lint primary(lint num)
{
    if (num < 2) return 0;
    else if (num == 2) return 1;
    else if (num % 2 == 0) return 0;
 
    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            return 0;
        }
    }
 
    return 1;
}
   long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
    lint lcm(lint a,lint b){
        return a/__gcd(a,b)*b;
    }
     lint gcd(lint a,lint b){
        return __gcd(a,b);
    }    
 lint ans=0;
 void dfs(lint n,lint c){
        if(c>n)return ;
            string s=to_string(c);
            lint count3=0;
            lint count5=0;
            lint count7=0;
            rep(i,s.size()){
                if(s[i]=='3')count3++;
                if(s[i]=='5')count5++;
                if(s[i]=='7')count7++;
            }
            if(count3&&count5&&count7)ans++;
        dfs(n,c*10+3);
        dfs(n,c*10+5);
        dfs(n,c*10+7);
 }      
  int main(){
      lint n;
      cin>>n;
      dfs(n,0);
      cout<<ans;
  }
  
     


Measured memory_bytes: 256
#include <iostream>
#include <climits>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#define INF_INT (INT_MAX / 2)
#define INF_LONG (LONG_MAX / 2)
//#define DEBUG true
#define DEBUG false
using namespace std;

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

  int n;
  cin >> n;
  string s;
  cin >> s;

  int sw[n + 1], se[n + 1];
  fill(sw, sw + n + 1, 0);
  fill(se, se + n + 1, 0);
  for(int i = 1; i <= n; i++){
    sw[i] = sw[i - 1];
    if(s[i - 1] == 'W') ++sw[i];
    se[i] = se[i - 1];
    if(s[n - i] == 'E') ++se[i];
  }

  int ans = INF_INT;
  for(int i = 0; i < n; i++){
    ans = min(ans, sw[i] + se[n - i - 1]);
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 2964
// 基本テンプレート
 
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
using namespace std;
 
#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define int long long int
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
typedef pair<int, int> pii;
typedef long long ll;
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1001001001001001LL;
const ll MOD = 1000000007LL;

const int BORD = 1010;
int A[100010], B[100010], ans[100010];

 
signed main() {
    int N, M; cin >> N >> M;
    vector< vector<int> > mod_rec(BORD);
    for(int i=0; i<BORD; i++) {
        mod_rec[i] = vector<int>(i);
    }

    for(int i=0; i<M; i++) {
        cin >> A[i] >> B[i];
        ans[0] += A[i] + 1;
        if(B[i] < BORD) {
            mod_rec[ B[i] ][B[i] - A[i] - 1] += B[i];
        }
        else {
            int init = B[i] - A[i] - 1;
            for(int k=init; k<N; k+=B[i]) {
                ans[k] -= B[i];
            }
        }
    }

    for(int i=0; i<N; i++) {
        if(i > 0) ans[i] += ans[i-1] + M;
        for(int j=1; j<BORD; j++) {
            int mod = i % j;
            ans[i] -= mod_rec[j][mod];
        }
        cout << ans[i] << endl;
    }
    return 0;
}


Measured memory_bytes: 9148
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN 10000
#define MAXK 9

int n,a,b,dig,tmp;
long long sum;
int n1,n2,n3,n4,n5;
int main(int argc,char const* argv[])
{
  long long ans=0;
  cin >> n >> a >> b;
  for(int i=1;i<=n;i++)
    {
      sum=0;
      tmp=i;
      while(tmp)
	{
	  dig=tmp%10;
	  sum=sum+dig;
	  tmp=tmp/10;
	}
      if(sum>=a && sum<=b) ans+=i;
    }
  cout << ans << endl;
  return 0;
}


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

vector<vector<int>>ab;
vector<int>qq,ans;

void trip(int sum,int cur,int pre){
	sum+=qq.at(cur);
	ans.at(cur)=sum;
	for(auto&&i:ab.at(cur)){
		if(i==pre)continue;
		trip(sum,i,cur);
	}
}

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int n,q; cin>>n>>q;
	ab.resize(n+1);
	for(int i=1;i<n;++i){
		int a,b; cin>>a>>b;
		ab.at(a).emplace_back(b);
		ab.at(b).emplace_back(a);
	}
	qq.resize(n+1,0);
	for(int i=0;i<q;++i){
		int p,x; cin>>p>>x;
		qq.at(p)+=x;
	}
	ans.resize(n+1,0);
	trip(0,1,-1);
	for(int i=1;i<=n;++i)cout<<ans.at(i)<<"\n"s;
}


Measured memory_bytes: 24988
#include<bits/stdc++.h>
using namespace std;
int maxn = 100000;
int eratoes[100005];
int similar[100005];
int main(){
	for(int i=2; i<=maxn; i++) eratoes[i] = i;
	for(int i=2; i*i<=maxn; i++){
		if(eratoes[i]==i){
			for(int j=i*i; j<=maxn; j+=i) eratoes[j] = i;
		}
	}
	for(int i=2; i<=maxn; i++){
		if(eratoes[i]==i && eratoes[(i+1)/2]==(i+1)/2)
			similar[i] = true;
	}
	for(int i=1; i<=maxn; i++) similar[i]+=similar[i-1];
	int q;
	cin>>q;
	while(q--){
		int a,b;
		cin>>a>>b;
		cout<<similar[b]-similar[a-1]<<'\n';
	}
}

Measured memory_bytes: 4380
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep2(i,a,b) for(int i=(a);i<(b);++i)

template<class T> inline void chmin(T& a, T b) {if (a > b) a = b;}
template<class T> inline void chmax(T& a, T b) {if (a < b) a = b;}

//vector出力
template <class T>ostream &operator<<(ostream &o,const vector<T>&v){
  o<<"{";
  for(int i=0;i<(int)v.size();i++) o << (i>0?", ":"") << v[i];
  o<<"}";
  return o;
}

ll const mod =1e9+7;
int main() {
  ll N;
  cin >> N;
  ll cnt=1,a;
  map<int,int> mp;
  rep(i,N) {
    cin >> a;
    mp[a]++;
  }
  for (auto i=mp.begin();i!=mp.end();i++){
    if (i->first!=0&&i->second!=2) {
      cout << 0 << endl; return 0;
    }
    cnt = cnt*i->second%mod;
  }
  cout << cnt << endl;
}

Measured memory_bytes: 3200
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<queue>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); i++)
typedef pair<int,int> pii;
typedef pair<int,pii> pip;

class Dijkstra{
private:
    struct edge {int to,cost;};
    vector<vector<edge> > g;
    int n;

public:
    Dijkstra(int size){
        g.resize(size);
        n = size;
    }
    vector<vector<int> > dist;
    void add(int a, int b, int c){
        edge e1 = {b,c}, e2 = {a,c};
        g[a].push_back(e1);
        g[b].push_back(e2);
    }
    int calc(int s,int t,int ma){
        priority_queue<pip,vector<pip>,greater<pip> > q;
        int n = g.size();
        dist = vector<vector<int> > (n, vector<int>(ma+1,1e9));
        dist[s][0] = 0;
        q.push(pip(0,pii(s,0)));
        while(!q.empty()){
            pip p = q.top();
            q.pop();
            int c = p.first;
            pii node = p.second;
            if(dist[node.first][node.second] < c)continue;
            rep(i,g[node.first].size()){
                edge e = g[node.first][i];
                if(dist[e.to][node.second] > dist[node.first][node.second] + e.cost){
                    dist[e.to][node.second] = dist[node.first][node.second] + e.cost;
                    q.push(pip(dist[e.to][node.second],pii(e.to,node.second)));
                }
                if(node.second < ma){
                    if(dist[e.to][node.second+1] > dist[node.first][node.second] + e.cost/2){
                        dist[e.to][node.second+1] = dist[node.first][node.second] + e.cost/2;
                        q.push(pip(dist[e.to][node.second+1],pii(e.to,node.second+1)));
                    }
                }
            }
        }
        int ret = 1e9;
        rep(i,ma+1)ret = min(ret, dist[t][i]);
        return ret;
    }
};

int main(){
    int c,n,m,s,d;
    while(cin >> c >> n >> m >> s >> d, n){
        Dijkstra dij(n);
        rep(i,m){
            int a,b,f;
            cin >> a >> b >> f;
            dij.add(a-1,b-1,f);
        }
        cout << dij.calc(s-1,d-1,c) << endl;
    }
}



Measured memory_bytes: 3184
#include<iostream>
using namespace std;
main(){
	int month[12]={31,29,31,30,31,30,31,31,30,31,30,31};
	string day[7]={"Wednesday","Thursday","Friday","Saturday","Sunday","Monday","Tuesday"};
	int n[2];
	while(cin>>n[0]>>n[1],n[0],n[1]){
		int sum=0;
		for(int i=0;i<n[0]-1;++i){
			sum+=month[i];
		}
		sum+=n[1];
		cout<<day[sum%7]<<endl;
	}
}

Measured memory_bytes: 1192
var
	N,i,id,sz,asz,t:Longint;
	pa,x:Array[1..1000]of Longint;
	dp:Array[1..1000]of int64;
	cum:Array[0..1]of int64;
	cumpa:Array[0..1]of Longint;
begin
	read(N);
	id:=1;
	for i:=1 to N do begin
		read(dp[i]);
		pa[i]:=0;
		t:=i and 1;
		if cum[t]>0 then begin
			inc(dp[i],cum[t]);
			pa[i]:=cumpa[t];
		end;
		if dp[i]>cum[t]then begin
			cum[t]:=dp[i];
			cumpa[t]:=i;
		end;
		if dp[id]<dp[i]then id:=i;
	end;
	writeln(dp[id]);
	while id>0 do begin
		inc(sz);
		x[sz]:=id;
		id:=pa[id];
	end;
	asz:=N-x[1]+x[sz]-1;
	for i:=2 to sz do begin
		t:=(x[i-1]-x[i])div 2;
		inc(asz,t);
	end;
	writeln(asz);
	for i:=N downto x[1]+1 do begin
		writeln(i);
	end;
	for i:=2 to sz do begin
		t:=(x[i-1]-x[i])div 2;
		while t>0 do begin
			writeln(x[i]+t);
			dec(t);
		end;
	end;
	for i:=1 to x[sz]-1 do begin
		writeln(1);
	end;
end.

Measured memory_bytes: 128
n = int(input())

cnt_3 = 0
i = 1
for i in range(n+1) :
    if i%3 == 0:
    	cnt_3 = cnt_3 + i

cnt_5 = 0
h = 1
for h in range(n+1) :
    if h%5 == 0:
    	cnt_5 = cnt_5 + h

cnt_35 = 0
j = 1
for j in range(n+1) :
    if j%3 == 0 and j%5 == 0:
    	cnt_35 = cnt_35 + j

print(int((1+n)*n/2 - (cnt_3 + cnt_5 - cnt_35)))


Measured memory_bytes: 9132
using System;
using System.Collections.Generic;
using System.Text;

namespace AtTest.ABC_103
{
    class B
    {
        static void Main(string[] args)
        {
            Method(args);
            Console.ReadLine();
        }

        static void Method(string[] args)
        {
            string s = Console.ReadLine();
            string t = Console.ReadLine();
            for (int i = 0; i <= s.Length; i++)
            {
                if (s.Equals(t))
                {
                    Console.WriteLine("Yes");
                    return;
                }
                string sub = s.Substring(0, s.Length - 1);
                s = s.Substring(s.Length - 1);
                s += sub;
                //Console.WriteLine(s);
            }
            Console.Write("No");
        }
    }
}


Measured memory_bytes: 11092
package main

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

var sc = bufio.NewScanner(os.Stdin)

func main() {
	sc.Split(bufio.ScanWords)
	n := readInt()
	var p int
	c := 0
	for i := 1; i <= n; i++ {
		p = readInt()
		if p != i {
			c++
		}
		if c > 2 {
			fmt.Println("NO")
			return
		}
	}
	fmt.Println("YES")
}

func read() string {
	sc.Scan()
	return sc.Text()
}

func readInt() int {
	i, e := strconv.Atoi(read())
	if e != nil {
		panic(e)
	}
	return i
}


Measured memory_bytes: 640
MOD = int(1e9 + 7)
N = int(1e5)
M = 13

s = input()
dp = [[0 for x in range(M)] for x in range(N+10)]
dp[0][0] = 1

for i in range(len(s)):
    for j in range(M):
        for k in range(10):
            if s[i] == "?" or s[i] == str(k):
                dp[i+1][(j*10 +k) % M] += dp[i][j]
                dp[i+1][(j*10 +k) % M] %= MOD


print(dp[len(s)][5])


Measured memory_bytes: 66396
// Created by: WeirdBugsButOkay

#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define ff first
#define ss second
#define PI 3.14159265358979323846

using namespace std;

int h, w, k;

void solve()
{
	int x1, x2, y1, y2;
	cin >> h >> w >> k;
	string s[h];
	cin >> x1 >> y1;
	cin >> x2 >> y2;
	for(int i = 0; i < h; i++)
		cin >> s[i];
	vector <vector <int> > dis(h, vector <int> (w, 1e9));
	vector <vector <bool> > vis(h, vector <bool> (w, 0));
	x1--, x2--, y1--, y2--;
	dis[x1][y1] = 0;
	int x[4] = {1, 0, -1, 0}, y[4] = {0, 1, 0, -1};
	queue <pair <int, int> > bfs;
	bfs.push({x1, y1});
	//cout << "Hi" << endl;
	auto ok = [&](int i, int j)
	{
		if(i >= h || i < 0)
			return false;
		if(j >= w || j < 0)
			return false;
		if(s[i][j] == '@')
			return false;
		return true;
	};
	vis[x1][y1] = 1;
	while(!bfs.empty())
	{
		auto p = bfs.front();
		bfs.pop();
		//cout << "at " << p.ff << "," << p.ss << endl;
		for(int j = 0; j < 4; j++)
		{
			for(int i = 1; i <= k; i++)
			{
				int xx = p.ff + i * x[j], yy = p.ss + i * y[j];
				if(!ok(xx, yy))
					break;
				if(dis[xx][yy] <= dis[p.ff][p.ss])
					break;
				dis[xx][yy] = dis[p.ff][p.ss] + 1;
				if(vis[xx][yy] == 0)
				{
					bfs.push({xx, yy});
					vis[xx][yy] = 1;
				}
			}
		}
		//cout << endl;
	}
	/*for(int i = 0; i < h; i++)
	{
		for(int j = 0; j < w; j++)
			cout << setw(12) << dis[i][j];
		cout << endl;
	}*/
	if(dis[x2][y2] == 1e9)
		cout << -1 << endl;
	else cout << dis[x2][y2] << endl;
}

int main()
{
	int q = 1;
	//scanf("%d", &q);
	for(int i = 1; i <= q; i++)
	{
		solve();
	}
	return 0;
}

Measured memory_bytes: 12160
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int read(){
    int x=0;bool f=0;char c=getchar();
    while(c<'0'||c>'9') f|=c=='-',c=getchar();
    while(c>='0'&&c<='9') x=x*10+(c^48),c=getchar();
    return f?-x:x;
}

#define MAXN 100000
#define LL long long

int N,X;
LL Sum[MAXN+5],Org,D[MAXN+5];
struct Range{
    LL tot;
    int l,r,id;
}A[MAXN+5];
bool cmp(Range i,Range j){
    return i.tot>j.tot;
}

bool Check(LL expt){
    LL Max=0;
    LL All=expt/X,Rest=expt%X;
    for(int i=1;i<=N;i++){
        LL l=min(Rest,D[A[i].id]);
        LL tmp=i>All?Sum[All]:(Sum[All+1]-A[i].tot);
        Max=max(Max,tmp+l*A[i].l+(Rest-l)*A[i].r);
    }
    return Max>=Org;
}

int main(){
    N=read(),X=read();
    for(int i=1;i<=N;i++){
        D[i]=read();
        A[i].id=i;
        A[i].l=read(),A[i].r=read();
        A[i].tot=D[i]*A[i].l+(X-D[i])*A[i].r;
        Org+=D[i]*A[i].l;
    }
    sort(A+1,A+N+1,cmp);
    for(int i=1;i<=N;i++)
        Sum[i]=Sum[i-1]+A[i].tot;
    LL Left=-1,Right=(LL)X*N;
    while(Left+1<Right){
        LL mid=(Left+Right)>>1;
        if(Check(mid))
            Right=mid;
        else
            Left=mid;
    }
    printf("%lld",Right);
}


Measured memory_bytes: 4096
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define EPS 0.0000000001
#define INF 1000000000
#define MOD 1000000007
typedef long long ll;

int main()
{
    int x;
    cin>>x;
    if(x<1200){
        cout<<"ABC"<<endl;
    }
    else{
        cout<<"ARC"<<endl;
    }
}


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

struct edge {
  int to;
  int cost;
};

int n;
vector<vector<edge>> G;
vector<int> d;

void daikstr(int s) {
  priority_queue<P, vector<P>, greater<P>> que;
  fill(d.begin(), d.end(), 1000000000);
  d[s] = 0;
  que.push(P(0, s));

  while(!que.empty()) {
    P p = que.top();
    que.pop();
    int v = p.second;
    if(d[v] < p.first) continue;

    for(int i = 0; i < G[v].size(); ++i) {
      edge e = G[v][i];
      if(d[e.to] > d[v] + e.cost) {
        d[e.to] = d[v] + e.cost;
        que.push(P(d[e.to], e.to));
      }
    }
  }
}

int main() {
  int x, y;
  scanf("%d %d %d", &n, &x, &y);
  d = vector<int>(n);
  vector<int> o(n);
  G = vector<vector<edge>>(n);
  for(int i = 0; i < n - 1; i++) {
    G[i].push_back({i + 1, 1});
    G[i + 1].push_back({i, 1});
  }
  G[x - 1].push_back({y - 1, 1});
  G[y - 1].push_back({x - 1, 1});
  for(int i = 0; i < n; i++) {
    daikstr(i);
    for(int j = 0; j < n; j++) {
      if(i == j) continue;
      o[d[j]]++;
    }
  }
  for(int i = 1; i < n; i++) printf("%d\n", o[i] / 2);
}

Measured memory_bytes: 384
n,m,k = gets.chomp.split(" ").map(&:to_i)
a_arr = [0] + gets.chomp.split(" ").map(&:to_i)
b_arr = gets.chomp.split(" ").map(&:to_i) + [10**9]

max = 0
sum_a = 0
sum_b = b_arr.sum
index_b = m + 1
a_arr.each_with_index do |a, i|
  sum_a += a

  if sum_a > k
    break
  elsif sum_a + sum_b <= k
    count = i + index_b
  else
    (index_b-1).downto(0) do |j|
      sum_b -= b_arr[j]
      index_b = j
      break if sum_a + sum_b <= k
    end
    count = i + index_b
  end

  max = count if count > max
end

puts max


Measured memory_bytes: 50892
#include <iostream>
#include <vector>

using namespace std;

bool sum_judge(const vector<int>& v, int current_i, int m)
{
    int next_m = m - v[current_i];
    int next_i = current_i + 1;

    if (next_m == 0){
        return true;
    } else if (next_i == v.size()){
        return false;
    }

    if (sum_judge(v, next_i, next_m)){
        return true;
    } else {
        return sum_judge(v, next_i, m);
    }
}

int main()
{
    int n;
    vector<int> A;
    int q;
    vector<int> m;

    cin >> n;
    A = vector<int>(n);
    for (int i = 0; i < n; i++) cin >> A[i];
    
    cin >> q;
    m = vector<int>(q);
    for (int i = 0; i < q; i++) cin >> m[i];

    for (int current_m : m){
        if (sum_judge(A, 0, current_m)) cout << "yes" << endl;
        else cout << "no" << endl;
    }

    return 0;
}




Measured memory_bytes: 3104
import core.bitop, std.algorithm, std.ascii, std.bigint, std.conv, std.math,
    std.functional, std.numeric, std.range, std.stdio, std.string, std.random,
    std.typecons, std.container, std.format;

// dfmt off
T lread(T = long)(){return readln.chomp.to!T();}
T[] lreads(T = long)(long n){return generate(()=>readln.chomp.to!T()).take(n).array();}
T[] aryread(T = long)(){return readln.split.to!(T[])();}
void scan(TList...)(ref TList Args){auto line = readln.split();
foreach (i, T; TList){T val = line[i].to!(T);Args[i] = val;}}
alias sread = () => readln.chomp();enum MOD = 10 ^^ 9 + 7;
alias PQueue(T, alias less = "a<b") = BinaryHeap!(Array!T, less);
// dfmt on

void main()
{
    long H, W;
    scan(H, W);
    auto S = new string[](H);
    foreach (i; 0 .. H)
        S[i] = sread();
    foreach (h; 0 .. H)
        foreach (w; 0 .. W)
            if (S[h][w] == '#')
            {
                if (0 < h && S[h - 1][w] == '#')
                    continue;
                if (h + 1 < H && S[h + 1][w] == '#')
                    continue;
                if (0 < w && S[h][w - 1] == '#')
                    continue;
                if (w + 1 < W && S[h][w + 1] == '#')
                    continue;
                writeln("No");
                return;
            }
    writeln("Yes");
}


Measured memory_bytes: 256
import sys
import re
import queue
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

def main():
	a,b,c,d = i_map()
	max_xy = max([a*c,b*c,a*d,b*d])

	print(max_xy)

	return


if __name__ == '__main__':
	main()

Measured memory_bytes: 10692
package main

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

func solve() {
	s := getRunes()

	ans := "Yes"
	for i, r := range s {
		switch (i + 1) % 2 {
		case 0:
			if r == 'R' {
				ans = "No"
			}
		case 1:
			if r == 'L' {
				ans = "No"
			}
		}
	}

	fmt.Fprintln(wr, ans)
}

// -----------------------------------------

const (
	inf = 1 << 60
	// mod = 1000000007
)

var (
	sc = bufio.NewScanner(os.Stdin)
	wr = bufio.NewWriter(os.Stdout)
)

func main() {
	// buf := 200001
	// sc.Buffer(make([]byte, buf), buf)
	sc.Split(bufio.ScanWords)
	solve()
	wr.Flush()
}

func getInt() int {
	sc.Scan()
	i, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	return i
}

func getIntSlice(n int) []int {
	is := make([]int, n)
	for i := range is {
		is[i] = getInt()
	}
	return is
}

func getString() string {
	sc.Scan()
	s := sc.Text()
	return s
}

func getRunes() []rune {
	return []rune(getString())
}


Measured memory_bytes: 640
a = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

k = int(input())

print(a[k-1])

Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n;
int t;
vector< vector<int> > A;
vector<int> c;
vector<int> d;
vector<int> f;

void dfsVisit(int u) {
    t++;
    d[u] = t;
    c[u] = 1;
    for(int i=0; i<A[u].size(); i++) {
        int v = A[u][i];
        if(c[v] == 0) dfsVisit(v);
    }
    t++;
    f[u] = t;
}

void dfs() {
    for(int u=0; u<n; u++) c[u] = 0;
    t = 0;
    for(int u=0; u<n; u++) {
        if(c[u] == 0) {
            dfsVisit(u);
        }
    }
}

int main() {
    cin >> n;
    A.resize(n);
    c.resize(n);
    d.resize(n);
    f.resize(n);

    for(int i=0; i<n; i++) {
        int u,k;
        cin >> u >> k;
        A[u-1].resize(k);
        for(int j=0; j<k; j++) {
            int v;
            cin >> v;
            A[u-1][j] = v-1;
        }
        sort(A[u-1].begin(), A[u-1].end());
    }

    dfs();
    for(int i=0; i<n; i++) cout << i+1 << " " << d[i] << " " << f[i] << endl;
}


Measured memory_bytes: 3092
#include<stdio.h>

typedef long long int LL;

double dp[3000][1501];

class solution {
private:
	double ar[3000];
	int n;
	double serc(int x, int p) {
		if (p < 0) p = 0;
		if (x == n) {
			if (p) return 0;
			return 1;
		}
		if (dp[x][p] > -1 + 1e-9) return dp[x][p];
		dp[x][p] = ar[x] * serc(x + 1, p - 1) + (1 - ar[x]) * serc(x + 1, p);
		return dp[x][p];
	}
	void reset() {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j <= n; j++) {
				dp[i][j] = -1;
			}
		}
	}
public:
	solution() {
		scanf("%d", &n);
		for (int i = 0; i < n; i++) {
			scanf("%lf", &ar[i]);
		}
		reset();
		printf("%.10f\n", serc(0, (n + 1) / 2));
	}
};

#ifndef L0C4L
int main() {
	solution();
	return 0;
}
#endif

Measured memory_bytes: 35584