akhauriyash/Code-Regression huggingface dataset:
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using P   = pair<ll, ll>;
using mat = vector<vector<ll>>;

void IOS() { ios::sync_with_stdio(false), cin.tie(0); }

const ll INF = 1e16;
const ll MOD = 1e9 + 7;
const ld EPS = 1e-12;

template <typename T>
void dump(T x) { cout << x << endl; }
void dumpf(ld x, int t) { cout << setprecision(t) << fixed << x << endl; }
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val) {
	fill((T *)array, (T *)(array + N), val);
}
inline ll mod(ll a, ll b) {
	if (a > 0) return a % b;
	if (a % b == 0) return 0;
	ll x = -a / b + 1;
	a += x * b;
	return a % b;
}
ll powm(ll a, ll b, ll c) {
	if (b == 0)
		return 1;
	else if (b % 2 == 0) {
		ll d = powm(a, b / 2, c);
		return (d * d) % c;
	} else
		return (a * powm(a, b - 1, c)) % c;
}
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

//ll dx[4] = {1, 0, -1, 0};
//ll dy[4] = {0, 1, 0, -1};

string a[] = {"01", "02", "03", "04", "05", "06", "07", "08", "09", "10", "11", "12"};

int main() {
	IOS();
	ll n, k;
	string s;
	cin >> s;
	bool t1 = false, t2 = false;
	for (int i = 0; i < 12; i++) {
		t1 |= s.substr(0, 2) == a[i];
		t2 |= s.substr(2, 2) == a[i];
	}
	if (t1 && t2) {
		dump("AMBIGUOUS");
	} else if (t1) {
		dump("MMYY");
	} else if (t2) {
		dump("YYMM");
	} else {
		dump("NA");
	}
	return 0;
}

Measured memory_bytes: 256
using System;

namespace OnlineJudge
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] str = Console.ReadLine().Split(' ');
            var a = int.Parse(str[0]);
            var b = int.Parse(str[1]);
            

            if (a < b)
            {
                Console.WriteLine("a < b");
            }
            else if(a > b)
            {
                Console.WriteLine("a > b");
            }
            else
            {
                Console.WriteLine("a == b");
            }
        }
    }
}


Measured memory_bytes: 8980
#define _USE_MATH_DEFINES

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
//#include <atcoder/all>
using namespace std;
//using namespace atcoder;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<ll, ll, ll> tl3;

//typedef modint998244353 mint;

const int BIG_NUM = 1e9;
const ll INF = 1000000000000000000;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;

const ll MAX = 1e9 + 5;

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

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

	vector<ll> sum(n + 1);
	for (int i = 0; i < n; i++) {
		sum[i + 1] = sum[i] + a[i];
	}

	int ans = n;
	for (int i = 1; i < n; i++) {
		if (2 * sum[i] < a[i]) {
			ans = n - i;
		}

	}
	cout << ans << endl;
}

Measured memory_bytes: 4784
//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0558
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;

int row, col, n;

struct point {
	int x, y;
};

char map[1010][1010];
int d[1010][1010];
int direct[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };

int BFS(int &startX, int &startY, char target) {
	memset(d,0,sizeof(d));

	queue<point> q;
	point p;
	p.x = startX;
	p.y = startY;
	d[startX][startY] = 0;
	q.push(p);
	while (!q.empty()) {
		int nowX = q.front().x,nowY = q.front().y;
		q.pop();

		if (map[nowX][nowY] == target) {
			startX = nowX;
			startY = nowY;
			return d[nowX][nowY];
		}

		int nextX, nextY;
		for (int i = 0; i < 4; i++) {
			nextX = nowX + direct[i][0];
			nextY = nowY + direct[i][1];

			if (nextX >= 0 && nextY >= 0 && nextX < row && nextY < col && 
					map[nextX][nextY] != 'X' && d[nextX][nextY] == 0) {
				d[nextX][nextY] = d[nowX][nowY] + 1;
				p.x = nextX;
				p.y = nextY;
				q.push(p);
			}
		}
	}
	return -1;
}

int main() {
	int startX, startY, sum = 0;

	scanf("%d%d%d", &row, &col, &n);
	for (int i = 0; i < row; i++) {
		scanf("%s", map[i]);
		for (int j = 0; j < col; j++) {
			if (map[i][j] == 'S') {
				startX = i;
				startY = j;
			}
		}
	}

	for (int i = 0; i < n; i++) {
		int dis = BFS(startX, startY, i + '1');
		sum += dis;
	}
	printf("%d\n", sum);
}


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


int main()
{
    int k, n;
    cin >> n >> k;
    vector<int> p(n);
    for (int i = 0; i < n; i++) cin >> p[i];

    vector<double> q(n + 1);
    for (int i = 1; i <= n; i++) q[i] = (p[i - 1] + 1) / 2.0;
    for (int i = 1; i <= n; i++) q[i] += q[i - 1];
    double maxv = 0;
    for (int i = k; i <= n; i++) maxv = max(maxv, q[i] - q[i - k]);
    cout << setprecision(12) << maxv << endl;
    return 0;
}


Measured memory_bytes: 2560
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <stack>
#include <queue>
#include <math.h>
#include <string>
#include <numeric>
#include <algorithm>
#include <utility>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;


// 68 11 55 - rank 3
// 69 12 19

int gcd(int a, int b) {
    while (b != 0) {
        auto na = a % b;
        a = b;
        b = na;
    }
    return a;
}


void oneCase() {
    string line;
    cin >> line;
    auto n = line.size();
    cout << line[0] << n - 2 << line.back() << "\n";

}


int main() {
    int t = 1;
//    cin >> t;
    while (t--) {
       oneCase();
    }

    return 0;
}

ll fact(ll n, ll mod) {
    ll res = 1;
    while (n > 0) {
        res = (res * n) % mod;
        --n;
    }
    return res;
}


Measured memory_bytes: 256
#include<bits//stdc++.h>
using namespace std;
int main(){
    int n, h, m, s;
    while(scanf("%d", &n), n){
        int imos[86401] = {};
        for(int i = 0; i < n; i++){
            scanf("%d:%d:%d", &h, &m, &s);
            imos[3600*h+60*m+s]++;
            scanf("%d:%d:%d", &h, &m, &s);
            imos[3600*h+60*m+s]--;
        }
        int ans = 0, sum = 0;
        for(int i = 0; i < 86401; i++){
            sum += imos[i];
            ans = max(ans, sum);
        }
        printf("%d\n", ans);
    }
}


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

int main(){
    int n;cin >> n;
    vector<vector<int>> vec(n,vector<int>(n));
    for(int i=0;i<n;i++){
        int j,k;cin >> j >> k;
        j--;
        for(int t = 0;t<k;t++){
            int s;cin >> s;s--;
            vec[j][s] = 1;
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cout << vec[i][j];
            if(j!=n-1) cout << " ";
            else cout << endl;
        }
    }
}


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

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
typedef double ld;

#define pb push_back
#define all(c) c.begin(),c.end()
#define allr(c) c.rbegin(),c.rend()
#define MOD 1
#define PI 3.14159265


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

    int n;
    cin >> n;
    int tn = n;
    int s = 0;
    while(n) {
        s += (n % 10);
        n /= 10;
    }
    if(tn % s) cout << "No" << endl;
    else cout << "Yes" << endl;

    return 0;
}


Measured memory_bytes: 256
import bisect
import cmath
import heapq
import itertools
import math
import operator
import os
import random
import re
import string
import sys
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from functools import lru_cache, reduce
from math import gcd
from operator import add, itemgetter, mul, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


k = int(sys.stdin.buffer.readline())

mod = 7% k
for i in range(1, k* 2):
    if mod == 0:
        print(i)
        exit()
    mod = (mod * 10 + 7) % k
else:
    print(-1)


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

int64_t lcm(int64_t x, int64_t y) {
  int64_t t;
  if(x<y) {
    t=x;
    x=y;
    y=t;
  }
  int64_t r=x*y,n=x%y;
  while(n!=0) {
    x=y;
    y=n;
    n=x%y;
  }
  return r/y;
}

int main() {
  int64_t A,B,C,D,p,q,r;
  cin >> A >> B >> C >> D;
  int64_t X=B-A+1, n=lcm(C,D);

  X-=B/C-(A-1)/C+B/D-(A-1)/D-B/n+(A-1)/n;

  cout << X << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		long a = in.nextLong(), b = in.nextLong();
		in.close();
		long targ = getGCD(a, b);

		// 素因数分解
		long cnt = 1;
		if ( targ != 0 && targ % 2 == 0 ) {
			targ /= 2;
			cnt++;
			while ( targ % 2 == 0 ) {
				targ /= 2;
			}
		}

		Long div = 3L;
		while ( div <= Math.sqrt(targ) ) {
			if ( targ % div == 0 ) {
				// System.out.println("div:" + div);
				cnt++;
			}
			while ( targ % div == 0 ) {
				targ /= div;
			}
			div += 2;
		}

		if ( targ != 1 ) cnt++;
		System.out.println(cnt);
	}

	private static long getGCD(long a, long b) {
		if ( b == 0 ) return a;
		else return getGCD(b, a % b);
	}
}


Measured memory_bytes: 31444
#include<iostream>
#include<cstring>
using namespace std;
int n, a[10], x;
int main() {
	while (true) {
		cin >> n;
		if (n == 0) { break; }
		memset(a, 0, sizeof(a));
		for (int i = 0; i < n; i++) {
			cin >> x;
			a[x]++;
		}
		for (int i = 0; i < 10; i++) {
			if (a[i] == 0) { cout << '-' << endl; }
			else {
				for (int j = 0; j < a[i]; j++) { cout << '*'; }
				cout << endl;
			}
		}
	}
}

Measured memory_bytes: 1148
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===
# 約数を列挙　n=10^12までいける
def make_divisors(n):
    divisors = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)

    # divisors.sort()
    divisors.remove(1)
    return divisors


def main():
    n = ni()

    ans = set()
    ans.add(n)
    for i in range(2, int(n ** (0.5)) + 1):
        tmp = n
        while tmp % i == 0:
            tmp //= i
        if (tmp - 1) % i == 0:
            ans.add(i)

    yaku = set(make_divisors(n - 1))

    ans = ans | yaku

    print(len(ans))


if __name__ == '__main__':
    main()


Measured memory_bytes: 11016
#include<bits/stdc++.h>
using namespace std;
const int inf=1e9+5;
int main()
{
    int n;
    cin>>n;
    int a[n+5];
    for(int i=0;i<n;i++) cin>>a[i];
    int dp[n+5];
    for(int i=0;i<n;i++) dp[i]=inf;
    dp[0]=0;
    for(int i=0;i<n;i++){
        for(int j:{i+1,i+2}){
            if(j<=n){
                dp[j]=min(dp[j],dp[i]+abs(a[i]-a[j]));
            }
        }
    }
    cout<<dp[n-1]<<endl;
}


Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        String score;
        score = new String();

        while(true){
            int m = sc.nextInt();
            int f = sc.nextInt();
            int r = sc.nextInt();
            if(m==-1 && f==-1 && r==-1) break;
            
            if(m==-1 || f==-1) score = "F";
            else if(m+f >= 80) score = "A";
            else if(m+f >= 65) score = "B";
            else if(m+f >= 50) score = "C";
            else if(m+f >= 30){
                score = "D";
                if(r >= 50) score = "C";
            } 
            else if(m+f < 30) score = "F";

            System.out.println(score);
        }
        sc.close();
    }
    
}


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

int main(void) {
  string s, t;
  cin >> s >> t;
  int n = t.size();
  for(int i = 0; i < s.size() - t.size() + 1; i++) {
    int R=0;
    for(int j = 0; j < t.size(); j++){
      if(s.at(i+j)!=t.at(j)){
        R++;
      }
    }
        if(n>R){
          n=R;
        }
  }
cout<<n<<endl;
	return 0;
}


Measured memory_bytes: 3564
#include <iostream>
#include <string>
#include <map>
#include <utility>
using namespace std;
typedef long long ll;
string S;
int N;
int main(){
	cin >> N >> S;
	map<pair<string,string>,ll> ml,mr;
	string L = S.substr(0,N),R = S.substr(N,N);
	for(int i=0;i<(1<<N);i++){
		string lr = "",lb = "",rr = "",rb = "";
		for(int j=0;j<N;j++){
			if(i & (1<<j)){
				lr += L[j];
				rr += R[N-1-j];
			}else{
				lb += L[j];
				rb += R[N-1-j];
			}
		}
//		cout << lr << " " << lb << endl;
		ml[make_pair(lr,lb)]++;
		mr[make_pair(rr,rb)]++;
	}
	ll ans = 0;
	for(auto x:ml){
		ans += x.second*mr[x.first];
	}
	cout << ans << endl;
}

Measured memory_bytes: 108288
#include<iostream>
#include<cstdio>
using namespace std;
int tile(int i,int j);
char memo[22][22];
int w,h;
int ii,jj;

int main(){
  while(1){
    cin >> w >> h;
    if(w==0&&h==0)break;
    for(int i=0;i<h;i++){
      cin >> memo[i];
      for(int j=0;j<w;j++){
	if(memo[i][j]=='@'){
	  ii=i;
	  jj=j;
	}
      }
    }
    int c=tile(ii,jj);
    cout << c << endl;
  }
}

int tile(int i,int j){
  if(i>=h||j>=w||i<0||j<0)return 0;
  if(memo[i][j]=='#') return 0;
  memo[i][j]='#';
  int ret=0;
  ret+=tile(i,j-1);
  ret+=tile(i,j+1);
  ret+=tile(i-1,j);
  ret+=tile(i+1,j);
  return ret+1;
}

Measured memory_bytes: 1176
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <bitset>
#include <utility>
#include <numeric>

using namespace std;

using ll = long long;
using ull = unsigned long long;

const ll inf = (ll)2e9;
const ll mod = (ll)1e9 + 7;

template<typename T> T gcd(T a, T b)
{
	return b ? gcd(b, a % b) : a;
}

int main()
{
	ll n, x;
	cin >> n >> x;

	vector<ll> a;
	a.push_back(x);
	for (int i = 0; i < n; i++)
	{
		ll y;
		cin >> y;

		a.push_back(y);
	}

	ll ans = abs(x - a.at(0));
	for (int i = 1; i < a.size(); i++)
	{
		ans = gcd(ans, abs(x - a.at(i)));
	}

	cout << ans << endl;
}


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

int main(){
    int x,y;
    while(1){
        cin >> x >> y ;
        if( x == 0 && y == 0) break;
        if(x>y) {cout << y << " " << x << endl;}
        else {cout << x << " " << y << endl;}
    }
}


Measured memory_bytes: 3048
#include<bits/stdc++.h>
using namespace std;
const long long INF = 1e7 + 1;
const long long MOD = 1000000007;
const long double PI = 3.1415926;
#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()
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;

ll n, m, k, ans = 0, sum = 0, cnt = 0;
string s;
//char c;

#define Endl endl


/*--------------------template--------------------*/


int main() {
    cin >> n >> m;
    if (n == 0 || m == 0) {
        cout << "Zero" << Endl;
    } else if (n*m < 0) {
        cout << "Zero" << Endl;
    } else if (n > 0 && m > 0) {
        cout << "Positive" << endl;
    } else {
        cout << ((m - n) % 2 ? "Positive" : "Negative") << Endl;
    }
}

Measured memory_bytes: 256
// Bismillahir Rahmanir Rahim
#include<bits/stdc++.h>
#include<iomanip>
typedef long long ll;
typedef unsigned long long ul;
#define pi acos(-1)
#define ll long long
#define ull unsigned long long
#define vec vector<ll>
#define f1(i,n) for(i=1;i<n;i++)
int i,j;
using namespace std;
int main()
{
   //freopen("a.txt","r",stdin);
  string st,ch,x;
  cin>>st;
  cin>>ch;
  for(int i=0;i<ch.size()-1;i++)
  {
      x+=ch[i];
  }
  if(x==st)cout<<"Yes\n";
  else cout<<"No\n";
}



Measured memory_bytes: 3632
H,W,M = map(int,input().split())
P = [0]*(H+1)
Q = [0]*(W+1)
A = set()
for k in range(M):
    a,b = map(int,input().split())
    P[a] += 1
    Q[b] += 1
    A.add((a,b))
Pmax = max(P)
Qmax = max(Q)
Pindex = []
Qindex = []
for i in range(H+1):
    if P[i] == Pmax:
        Pindex.append(i)
for i in range(W+1):
    if Q[i] == Qmax:
        Qindex.append(i)
ans = Pmax+Qmax-1
key = 0
for x in Pindex:
  for y in Qindex:
    if (x,y) not in A:
      ans += 1
      key = 1
      break
  if key == 1:
    break
print(ans)


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

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define  inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define  dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define UB upper_bound
#define LB lower_bound
#define PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(it, v) for(auto it =  v.begin(); it !=  v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)

template<typename T> bool   setmin(T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool   setmax(T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

string s;

int main() {
	cin >> s;
	
	cout << (s[0] == s[2] ? "Yes" : "No") << endl;
	
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
using namespace std;
int main(){
	long long int n, k;
	cin >> n >> k;

	long long int x = n / k;
	if(abs(n-k*x)>abs(n-k*(x+1))){
		cout << abs(n - k * (x + 1));
	}else{
		cout << abs(n - k * x);
	}

	return 0;
} 


Measured memory_bytes: 256
#! python3
# bubble_sort.py

# 泡が上がっていくようにソーティングされる

N = int(input())
A = [int(x) for x in input().split(' ')]

exc_num = 0
flag = True
while flag:
    flag = False
    for i in range(N-1, 0, -1):
        if A[i] < A[i-1]:
            exc_num += 1
            A[i-1], A[i] = A[i], A[i-1]
            flag = True

print(' '.join([str(x) for x in A]))
print(exc_num)


Measured memory_bytes: 5604
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.List;
import java.util.Arrays;
import java.util.AbstractCollection;
import java.util.Map;
import java.util.Scanner;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Collections;
import java.util.ArrayList;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        E solver = new E();
        solver.solve(1, in, out);
        out.close();
    }

    static class E {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int N = in.nextInt();
            int M = in.nextInt();
            Map<Integer, List<Integer>> map = new HashMap<>();
            for (int i = 0; i < M; i++) {
                int u = in.nextInt();
                map.put(u, map.getOrDefault(u, new ArrayList<>()));
                map.get(u).add(in.nextInt());
            }
            int S = in.nextInt();
            int T = in.nextInt();

            int[][] memo;
            memo = new int[N + 1][4];
            for (int i = 0; i < N + 1; i++) {
                Arrays.fill(memo[i], -1);
            }
            memo[S][0] = 0;

            LinkedList<List<Integer>> que = new LinkedList<>();
            que.add(Arrays.asList(S, 0));
            while (!que.isEmpty()) {
                List<Integer> l = que.removeFirst();
                int s = l.get(0);
                int kenkenpa = l.get(1);
                if (s == T && kenkenpa == 3) {
                    out.println(memo[s][kenkenpa] / 3);
                    return;
                }
                int temp = (kenkenpa % 3) + 1;
                for (int u : map.getOrDefault(s, Collections.emptyList())) {
                    if (memo[u][temp] > 0) {
                        continue;
                    }
                    memo[u][temp] = memo[s][kenkenpa] + 1;
                    que.add(Arrays.asList(u, temp));
                }
            }
            out.println(-1);
        }

    }
}



Measured memory_bytes: 104280
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
using namespace std;

int main(){
    int n,k;
    cin >> n >> k;
    
    if (n>=10){
        cout << k << endl;
    }else {
        cout<<(k+100*(10-n))<<endl;
    }
}
    

Measured memory_bytes: 256
import std.stdio, std.conv, std.string, std.array, std.math, std.regex, std.range, std.ascii, std.numeric, std.random;
import std.typecons, std.functional, std.traits,std.concurrency;
import std.algorithm, std.container;
import core.bitop, core.time, core.memory;
import std.bitmanip;
import std.regex;

enum INF = long.max/3;
enum MOD = 10L^^9+7;

//辞書順順列はiota(1,N),nextPermituionを使う


void end(T)(T v)
if(isIntegral!T||isSomeString!T||isSomeChar!T)
{
    import core.stdc.stdlib;
    writeln(v);
    exit(0);
}

T[] scanArray(T = long)()
{
    static char[] scanBuf;
    readln(scanBuf);
    return scanBuf.split.to!(T[]);
}

dchar scanChar()
{
    int c = ' ';
    while (isWhite(c) && c != -1)
    {
        c = getchar;
    }
    return cast(dchar)c;
}

T scanElem(T = long)()
{
    import core.stdc.stdlib;
    static auto scanBuf = appender!(char[])([]);

    scanBuf.clear;

    int c = ' ';
    while (isWhite(c) && c != -1)
    {
        c = getchar;
    }
    while (!isWhite(c) && c != -1)
    {
        scanBuf ~= cast(char) c;
        c = getchar;
    }
    return scanBuf.data.to!T;
}

dchar[] scanString(){
    return scanElem!(dchar[]);
}


void main()
{
  auto a=scanString;
  auto b=scanString;
  auto c=scanString;
  if(a[$-1]==b[0]&&b[$-1]==c[0])end("YES");end("NO");
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define bug(x) cout << #x << " = " << x << endl
#define F first
#define S second
using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;
int main(){
    int n,m,Ti[51]={0},t;
    pii st[51],ck[51];
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>st[i].F>>st[i].S;
    for(int i=1;i<=m;i++) cin>>ck[i].F>>ck[i].S;
    for(int i=1;i<=n;i++){
        int dis=1e9;
        for(int j=1;j<=m;j++){
            t=abs(st[i].F-ck[j].F)+abs(st[i].S-ck[j].S);
            if(t<dis){
                Ti[i]=j;
                dis=t;
            }
        }
    }
    for(int i=1;i<=n-1;i++) cout<<Ti[i]<<endl;
    cout<<Ti[n];
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<cstdio>
#include<algorithm>

using namespace std;

int main(){
  vector<int> S, T;

  int n;
  scanf("%d", &n);
  for(int i = 0; i < n; i++){
    int s;
    scanf("%d", &s);
    S.push_back(s);
  }



  int q;
  scanf("%d", &q);
  for(int i = 0; i < q; i++){
    int t;
    scanf("%d", &t);
    T.push_back(t);
  }
  
//  printf("%d\n", (int)S.size());

  sort(S.begin(), S.end());
  S.erase(unique(S.begin(), S.end()), S.end());


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

  int i = 0;
  int j = 0;
  int ans = 0;

  while(i < S.size() && j < T.size()){
    if(S[i] == T[j]){
      ans++;
      i++;
      j++;
    }else if(S[i] > T[j]){
      j++;
    }else{
      i++;
    }
  }
  cout << ans << endl;
}



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

using namespace std;

int main() {
  int N, A;
  int n;
  
  cin >> N >> A;
  
  n = N / 500;
  if(N - n * 500 <= A) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 3600
#include <bits/stdc++.h>
#define endl '\n';
typedef long long ll;
const ll INF = 1e17 + 1;
const ll MAX = 2147483647;
const ll MOD = 1000003;

using namespace std;

ll min(ll x, ll y, ll z)
{
    return min(min(x, y), z);
}
ll max(ll x, ll y, ll z)
{
    return max(max(x, y), z);
}

ll min(ll x, ll y, ll z, ll o)
{
    return min(min(x, y, z), o);
}

ll _power(ll b, ll p)
{
    ll res = 1;
    while (p)
    {
        if (p % 2)
            res = (res * b) % MOD;
        b = (b * b) % MOD;
        p /= 2;
    }
    return res;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    double sum = 0.0;
    for(int i = 0; i<n; i++)
    {
        double x;
        cin >> x;
        sum += (1.0/x);
    }
    cout << (1.0/sum);

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;

int main(int argc, char const *argv[]) {
    std::string S;
    std::cin >> S;
    char prev = 'f';
    ll ans = 0;
    for (size_t i = 0; i < S.size(); i++) {
        if (S[i] != prev) {
            ans++;
        }
        prev = S[i];
    }
    std::cout << ans - 1 << '\n';
    return 0;
}


Measured memory_bytes: 512
N=int(input())
for h in range(1,3501):
    for n in range(1,3501):
        if (4*h*n-N*h-N*n) > 0 and (N*h*n)%(4*h*n-N*h-N*n) == 0:
            print(h,n,(N*h*n)//(4*h*n-N*h-N*n))
            exit()

Measured memory_bytes: 3060
import java.util.Map.Entry;
import java.io.*;
import java.util.*;

public class Main {
	
	public static void main(String[] args) throws IOException {
		FastScanner sc = new FastScanner(System.in);
		
		int n = 100000;
		boolean[] arr = new boolean[n+1];
		for(int i = 2; i <= n; i++){
			if(arr[i]) continue;
			for(int j = i+i; j <= n; j += i){
				arr[j] = true;
			}
		}
		
		int[] sum = new int[n+1];
		for(int i = 2; i <= n; i++){
			sum[i] = sum[i-1] + ((i % 2 != 0 && !arr[i] && !arr[(i+1)/2]) ? 1 : 0);
		}
		
		int Q = sc.nextInt();
		for(int i = 0; i < Q; i++){
			int L = sc.nextInt();
			int R = sc.nextInt();
			System.out.println(sum[R]-sum[L-1]);
		}
	}
}

class FastScanner {
    private InputStream in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    public FastScanner(InputStream in) {
		this.in = in;
	}
    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: 39780
fn main() {
    let v = read_vec::<i32>();
    let w = v[0];
    let a = v[1];
    let b = v[2];
    println!("{}", std::cmp::max((a - b).abs() - w, 0));
}

#[allow(dead_code)]
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}
#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}
#[allow(dead_code)]
fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}
#[allow(dead_code)]
fn yn(result: bool) {
    if result {
        println!("Yes");
    } else {
        println!("No");
    }
}


Measured memory_bytes: 4352
import java.util.Scanner;

public class Main {
	static Scanner in = new Scanner(System.in);
	public static void main(String[] args) {
		String str = in.nextLine();
		int s = 0, t = 0;
		for(int i = 0; i < str.length(); i++){
			if(str.charAt(i) == 'S'){
				s++;
			}else if(str.charAt(i) == 'T' && s > 0){
				s--;
			}else{
				t++;
			}
		}
		System.out.println(s + t);
	}
}


Measured memory_bytes: 26308
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll=long long;
using vi = vector<int>;
using Graph = vector<vi>;
using P = pair<int,int>;
const int MOD=(int)1e9+7;
const int INF=(int)1e9;
const ll LINF=(ll)1e18;

int main(){
    unsigned long long h,w;
    cin >> h >> w;
    unsigned long long ans;
    if(h==1 || w==1){
        ans = 1;
    }
    else if(h*w%2LL==0) ans = h*w/2LL;
    else ans = h*w/2LL + 1LL;
    cout << ans << endl;
}

Measured memory_bytes: 256
import sys
from operator import itemgetter
from collections import deque, Counter
from itertools import permutations, combinations
from heapq import heapify, heappop, heappush
from bisect import bisect, bisect_left

def search(n, x, m, K, D):
    ini = x % m
    modD = [D[i] % m for i in range(K)]
    roop , rem = (n - 1) // K, (n - 1) % K
    last = ini
    equal = 0
    for i in range(K):
        if i < rem and rem > 0:
            if modD[i] == 0: equal += roop + 1
            else: last += (roop + 1) * modD[i]
        else:
            if modD[i] == 0: equal += roop
            else: last += roop * modD[i]
    up = (last // m) - (ini // m)
    return n - 1 - equal - up

def solve():
    input = sys.stdin.readline
    K, Q = map(int, input().split())
    D = [int(d) for d in input().split()]
    Ans = []
    for _ in range(Q):
        n, x, m = map(int, input().split())
        Ans.append(search(n, x, m, K, D))

    for i, a in enumerate(Ans): print(a)

    return 0

if __name__ == "__main__":
    solve()

Measured memory_bytes: 55900
from collections import Counter
n=int(input())
c=input()
co=Counter(c)
wcnt=co["W"]
rcnt=co["R"]
if wcnt==0 or rcnt==0:
    print(0)
    quit()
ans=0
for i in range(n):
    if c[i]=="W" and i<rcnt:
        ans+=1

print(min(ans,rcnt))
        


Measured memory_bytes: 9660
#include<iostream>
using namespace std;
int main()
{
	int n;
	cin>>n;
	if(n==1)cout<<1<<endl;
	else if(n<4)cout<<2<<endl;
	else if(n<8)cout<<4<<endl;
	else if(n<16)cout<<8<<endl;
	else if(n<32)cout<<16<<endl;
	else if(n<64)cout<<32<<endl;
	else cout<<64<<endl;
	return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
N = int(input())
X = list(map(int, input().split()))

min_x = X[0]
max_x = X[0]
for i in range(N):
  if X[i] > max_x: max_x = X[i]
  if X[i] < min_x: min_x = X[i]

ans = 10000000
for p in range(min_x, max_x+1):
  ans_p = 0
  for x in X:
    ans_p += (x-p)**2
  if ans > ans_p: ans = ans_p

print(ans)

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

int main() {
  int H,W,i,j,k,l;
  string S,SC;
  cin >> H >> W;
  for(i=0;i<H;++i){
    cin >> SC;
    S += SC;
  }
  for(i=0;i<H;++i)
    for(j=0;j<W;++j)
      if(S.at(i*W+j)=='#')
        for(k=(i-(i>0)) ; k<(i+1+(i<(H-1))) ; ++k)
          for(l=(j-(j>0)) ; l<(j+1+(j<(W-1))) ; ++l)
            if(S.at(k*W+l)!='#')
              S.at(k*W+l)+=1;
  for(i=0;i<H;++i){
    for(j=0;j<W;++j){
      if(S.at(i*W+j)!='#')
        S.at(i*W+j) += '0' - '.';
      cout << S.at(i*W+j);
    }
    cout << endl;
  }
}


Measured memory_bytes: 3636
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<iomanip>
using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
#define MOD 1000000007
#define LINF (long long)4e18

using ll = long long;


int main(){
   string S;
   cin >> S;
   vector<int> P(4);
   rep(i,4){
      P[i] = S[i] - '0';
   }

   rep(bit, 1 << 3){
      vector<char> o(3);
      int sum = P[0];
      rep(i,3){
         if(bit & 1 << i){
            sum += P[i+1];
            o[i] = '+';
         }
         else{
            sum -= P[i+1];
            o[i] = '-';
         } 
      }
      if(sum == 7){
         rep(i,3){
            cout << P[i] << o[i];
         }
         cout << P[3] << "=7" <<  endl;
         return 0;
      }
   }
   
}



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

int main(){
    int t, d, l, x;
    while(cin >> t >> d >> l, t+d+l){
        int rest = 0, ans = 0;
        while(t-- > 0){
            cin >> x;
            if(x >= l)  rest = d;
            if(rest > 0){
                ans++;
                rest--;
            }
        }
        cout << max(ans-1, 0) << endl;
    }
    return 0;
}


Measured memory_bytes: 3080
// -----------------------------------
// Author     : MatsuTaku
// Affiliation: Tokushima University
// Country    : Japan
// Date       : 04/05/2020
// -----------------------------------

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

vector<int> graph[10000];
vector<int> ans(10000), C(10000);
int dfs(int s, int p, int i) {
  ans[s] = C[i];
  for (auto t : graph[s]) {
    if (t==p) continue;
    i = dfs(t, s, i+1);
  }
  return i;
}

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

  int n; cin>>n;
  for (int i = 0; i < n-1; i++) {
    int a,b; cin>>a>>b; a--; b--;
    graph[a].push_back(b);
    graph[b].push_back(a);
  }
  for (int i = 0; i < n; i++)
    cin>>C[i];
  sort(C.rbegin(), C.rend());
  dfs(0, -1, 0);
  cout << accumulate(C.begin()+1,C.end(), 0ll) << endl;
  for (int i = 0; i < n; i++)
    cout << ans[i] << " ";
  cout << endl;

  return 0;
}


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

using namespace std;
using ll = long long;

int popcnt(ll a) {
    int res = 0;
    while(a > 0) {
        if(a & 1LL) res++;
        a /= 2;
    }
    return res;
}

int chunk_num(ll a, const int i) {
    int res = 0;
    for(int j = 0; j < i; j++) {
        if(a & (1LL << j)) res++;
    }
    return res;
}

int main() {
    int H, W, K;
    cin >> H >> W >> K;
    vector< vector<int> > S(H, vector<int>(W));
    for(auto &row : S)
        for(auto &c: row) {
            char x;
            cin >> x;
            c = x - '0';
        }
    
    int res = INT_MAX;
    for(ll i = 0; i < (1 << (H - 1)); i++) {
        int cut_num = popcnt(i);
        vector<int> chunk(1 + cut_num, 0);
        vector<int> chunk_hist(1 + cut_num, 0);
        //それぞれのchunkがK以下になるように切れば良い
        for(int w = 0; w < W; w++) {
            for(int h = 0; h < H; h++) {
                if(S[h][w] == 1) {
                    int ch = chunk_num(i, h);
                    chunk[ch]++;
                    if(chunk[ch] + chunk_hist[ch] > K) {
                        if(chunk_hist[ch] == 0) {
                            //どう切ってもKより大きくなる=手詰まり
                            cut_num = INT_MAX;
                            goto next_loop;
                        }
                        for(auto &x: chunk_hist) x = 0;
                        cut_num++;
                    }
                }
            }
            for(int i = 0; i < chunk.size(); i++) {
                chunk_hist[i] += chunk[i];
                chunk[i] = 0;
            }
        }

        next_loop:
        //cout << i << " " << cut_num << endl;
        res = min(res, cut_num);
    }

    cout << res << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int,int>;
#define For(i,a,b) for(int i=a;i<=b;i++)
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define MOD (ll)(998244353)
#define INF (2e9)
#define EPS (1e-6)
#ifdef LOCAL_TEST
#define debug(...) do{\
	cerr<<__PRETTY_FUNCTION__<<" - "<<__LINE__<<\
	" : ("#__VA_ARGS__<<") = ";\
	_OUT(__VA_ARGS__);\
}while(0)
template<typename T>void _OUT(T x){cerr<<x<<endl;}
template<typename T,typename...I>void _OUT(T x,I ...tail){cerr<<x<<", ";_OUT(tail...);}
#else
#define debug(...)
#endif

void INIT(){
#ifdef LOCAL_TEST
	freopen("D:\\input.in","r",stdin);
	freopen("D:\\output.out","w",stdout);
	freopen("D:\\error.out","w",stderr);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0);
}

ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }
ll lcm(ll a,ll b) { return a/gcd(a,b)*b; }
ll fpow(ll b,ll p){
	b%=MOD;
	ll ans=1;
	while(p>0){
		if(p&1) ans=(ans*b)%MOD;
		p/=2;
		b=(b*b)%MOD;
	}
	return ans;
}

int32_t main() {
	INIT();
	//code...
	int n,m,k; cin>>n>>m>>k;
	vector<ll> a(n+1),b(m+1);
	a[0]=0;
	For(i,1,n){
		cin>>a[i];
		a[i]+=a[i-1];
	}
	b[0]=0;
	For(i,1,m){
		cin>>b[i];
		b[i]+=b[i-1];
	}
	int ans=0;
	For(i,0,n){
		int it=(upper_bound(all(b),k-a[i])-b.begin())-1;
		if(it<0) break;
		ans=max(ans,i+it);
	}
	cout<<ans<<"\n";
	return 0;
}


Measured memory_bytes: 6368
n, k = map(int, input().split())
S = input()

compress = []
now = '1'
count = 0
for s in S:
    if s != now:
        compress.append(count)
        now = s
        count = 1
    else:
        count += 1
compress.append(count)

length = len(compress)
candidate = sum(compress[:2*k+1])
ans = candidate
if length <= 2*k+1:
    print(ans)
    exit()

for i in range(0, length-2*k-1, 2):
    if 2*k+2+i < length:
        candidate += compress[2*k+1+i] + compress[2*k+2+i] - compress[i] - compress[i+1]
    else:
        candidate += compress[2*k+1+i] - compress[i] - compress[i+1]
    ans = max(ans, candidate)

print(ans)


Measured memory_bytes: 4596
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#include<limits>
#include<map>
#define ll long long
#define ALL(x) (x).begin(),(x).end()
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define int_INF 2147483647
#define ll_INF 	9223372036854775807
#define MOD 1000000007
#define vi vector<int>
#define vii vector<vector<int>>
#define vll vector<long long>
#define pii pair<int,int>
using namespace std;

int main() {
	int N, M;
	cin >> N >> M;
	vll broken(100000), Ans(100000+1);
	fill(broken.begin(), broken.end(),ll_INF);
	for (int i = 0; i < M; i++) {
		cin >> broken[i];
	}
	Ans[0] = 1;
	if (broken[0] != 1) {
		Ans[1] = 1;
	}
	else {
		Ans[1] = 0;
	}

	for (int j = 2; j < N + 1; j++) {
		if (!binary_search(ALL(broken), j - 2)) {
			Ans[j] += Ans[j - 2];
			Ans[j] %= MOD;
		}
		if (!binary_search(ALL(broken), j - 1)) {
			Ans[j] += Ans[j - 1];
			Ans[j] %= MOD;
		}

		Ans[j] %= MOD;
	}

	cout << Ans[N] << endl;
}


Measured memory_bytes: 1792
#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;

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

#define ALL(v) v.begin(),v.end()
#define pb push_back
#define mp make_pair
#define F first
#define S second

#define UNIQUE(v) do{sort(v.begin(), v.end()); v.erase( unique(v.begin(), v.end()), v.end() );} while(0)


#define y0 y3487465
#define y1 y8687969

#define m0(x) memset(x,0,sizeof(x))
#define m1(x) memset(x,63,sizeof(x))

typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pi> vpi;
typedef vector<ll> vll;
typedef vector<vll> vvll;

double EPS = 1e-9;
int INFi = 1000000005;
long long INFll = 1000000000000000005ll;
double PI = acos(-1);
int dirx[8] = {-1,0,0,1,-1,-1,1,1};
int diry[8] = {0,1,-1,0,-1,1,-1,1};
ll MOD = 1000000007;

ll N, M;
const ll MAX_NM = 2000;
int S[MAX_NM], T[MAX_NM];

int main(){
  cin >> N >> M;
  REP(i, N) cin >> S[i];
  REP(j, M) cin >> T[j];

  ll dp[N + 1][M + 1];
  REP(i, N + 1) dp[i][0] = 1;
  REP(j, M + 1) dp[0][j] = 1;

  REP(i, N) {
    REP(j, M) {
      dp[i + 1][j + 1] = dp[i + 1][j] - dp[i][j] + dp[i][j + 1] + MOD;
      if(S[i] == T[j]) dp[i + 1][j + 1] += dp[i][j];
      dp[i + 1][j + 1] %= MOD;
    }
  }

  cout << dp[N][M] << endl;

  return 0;
}


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

int main() {
    string S;
    cin >> S;
    if (S[0] == 'S') cout << "Cloudy" << endl;
    if (S[0] == 'C') cout << "Rainy" << endl;
    if (S[0] == 'R') cout << "Sunny" << endl;
    return 0;
}


Measured memory_bytes: 3544
#include<iostream>
#include<list>
#include<vector>
#include<algorithm>
#include<string>
#include<stdio.h>
#include<math.h>
#include<unordered_map>
#include<map>

using namespace std;
using ll = long long;
using vec = vector<ll>;
using mat = vector<vec>;
using lst = list<int>;


class Ken
{
public:
	Ken(int n,int c,int k)
	{
		node = n;
		cost = c;
		kenpa = k;
	}
	int node;
	int cost;
	int kenpa;
};


int main()
{
	int N, M;
	cin >> N >> M;
	vector<lst> edge(N);
	for(int i=0;i<M;++i)
	{
		int u, v;
		cin >> u >> v;
		--u; --v;

		edge[u].push_back(v);
	}

	mat used(N, vec(3, 0));

	int S, T;
	cin >> S >> T;
	--S; --T;
	used[S][0] = 1;
	list<Ken> ken;
	ken.emplace_back(S, 0, 0);

	while (!ken.empty())
	{
		auto & k = ken.front();
		int kenpa = (k.kenpa + 1) % 3;
		for (auto u : edge[k.node])
		{	
			if (u == T&&kenpa == 0)
			{
				cout << k.cost + 1 << endl;
				return 0;
			}
			if (used[u][kenpa])continue;


			used[u][kenpa] = 1;
			ken.emplace_back(u, k.cost + (kenpa == 0), kenpa);
		}
		ken.pop_front();
	}
	cout << -1 << endl;

	return 0;
}

Measured memory_bytes: 10368
#include<iostream>
using namespace std;
int main(){
    long long m,d,c,sum=0LL,ans=0LL;
    cin>>m;
    for(int i=0;i<m;i++){
        cin>>d>>c;
        sum+=d*c;
        ans+=c;
    }
    cout<<ans-1+(sum-1)/9<<endl;
    return 0;
}

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

#define REP(i, x) for (int i = 0; i < (int)(x); i++)
#define REPS(i, x) for (int i = 1; i <= (int)(x); i++)

int main(int argc, char *argv[])
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int w, n, a, b;
    char c;
    cin >> w >> n;

    vector<int> kuji(w);
    REP(i, w) kuji[i] = i + 1;

    REP(i, n)
    {
        cin >> a >> c >> b;
        swap(kuji[a-1], kuji[b-1]);
    }

    REP(i, w) cout << kuji[i] << endl;
    
    return 0;
}



Measured memory_bytes: 3112
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define fi first
#define se second
#define pb push_back
#define mk make_pair
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const ll MOD = 1e9+7;

ll fastpowMOD(ll a, ll p,ll MOD);
ll fastpowMOD(ll a, ll p,ll MOD){ if(p==0) return 1; a %= MOD; ll z = fastpowMOD(a,p/2,MOD); z = (z*z)%MOD; if(p%2) z = (z*a)%MOD; return z; }

ll lcm(ll a,ll b){
	return (a*b)/__gcd(a,b);
}



int main(){
	fastio;
	ll h,n;
	cin>>h>>n;
	ll sum = 0;
	for(ll i=0;i<n;i++){
		ll x;
		cin>>x;
		sum += x;
	}
	if(sum>=h){
		cout<<"Yes\n";
	}
	else{
		cout<<"No\n";
	}
}


















Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<algorithm>
#include<utility>
#include<math.h>
#include<cstdlib>
#define rep(i, n) for(int i=0;i<n;i++)
#define repb(i, a, b) for(int i=a;i<b;i++)

using namespace std;
typedef pair<int, int> P;
typedef long long int ll;

const int INF = 1<<30;

int main(){
  int h, w;cin>>h>>w;
  vector<vector<int>> coin(h+1, vector<int>(w));
  vector<pair<P, P>> ans;
  rep(i, h)rep(j, w)cin>>coin[i][j];
  rep(i, h){
  	rep(j, w){
      if((coin[i][j]&1)==0)continue;
      if(j==w-1){
        coin[i][j]--;coin[i+1][j]++;
        if(i+1<h)ans.push_back(make_pair(P(i+1, j+1), P(i+2, j+1)));
      }else{
        coin[i][j]--;coin[i][j+1]++;
        ans.push_back(make_pair(P(i+1, j+1), P(i+1, j+2)));
      }
    }
  }
  int n=(int)ans.size();
  cout<<n<<endl;
  for(auto& e: ans){
  	cout<<e.first.first<<" "<<e.first.second<<" "<<e.second.first<<" "<<e.second.second<<endl;
  }
  return 0;
}


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

dic = {}

for i in range(n):
    s = sorted(input())
    temp = "".join(s)
    if temp not in dic:
        dic[temp] = 1
    else:
        dic[temp] += 1
    
ans = 0
for i in dic.values():
    ans += i*(i-1)/2

print(int(ans))

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

using namespace std;

int n;
int a[100000][3];
int dp[100001][4];

int solve(int i, int p)
{
	if (i == n + 1)
		return 0;
	if (dp[i][p] != -1)
		return dp[i][p];
	int ans = 0;
	for (int j = 1; j <= 3; j++)
	{
		if (j == p)
			continue;
		ans = max(ans, a[i - 1][j - 1] + solve(i + 1, j));
	}
	return dp[i][p] = ans;
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i][0] >> a[i][1] >> a[i][2];
	memset(dp, -1, sizeof(dp));
	cout << solve(1, 0) << endl;
	return 0;
}


Measured memory_bytes: 10752
#include <stdio.h>
int main(){
	int a,b,c,d,n,i=0;
	while(scanf("%d",&n)!=EOF){
		for(a=0;a<10;a++){
			for(b=0;b<10;b++){
				for(c=0;c<10;c++){
					for(d=0;d<10;d++){
						if((a+b+c+d)==n)i++;
					}
				}
			}
		}
		printf("%d\n",i);
		i=0;
	}
	return 0;
}

Measured memory_bytes: 0
H,W,h,w = map(int,input().split())
if H % h == 0 and W % w == 0:
  print("No")
else:
  print("Yes")
  ans = [[1000] * W for i in range(H)]
  num = 0
  for i in range(h-1,H,h):
    for j in range(w-1,W,w):
      ans[i][j] = -(h * w-1) * 1000-1
      num += 1
  for nu in ans:
    print(" ".join(map(str,nu)))

Measured memory_bytes: 10356