akhauriyash/Code-Regression huggingface dataset:
#最大公約数
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

#最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

#エストラテネスの篩
def isPrime():
    MAX = 10**5
    is_prime = [1] * (MAX+1)
    is_prime[0] = 0
    is_prime[1] = 0
    for i in range(2, MAX+1):
        if is_prime[i]:
            for j in range(i*2, MAX+1, i):
                is_prime[j] = 0
    return is_prime

#約数を求める
def makeDivisor(n):
    divisors = []
    for i in range(1, int(n ** 0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

#素因数分解（試し割り法）
def makePrime(n):
    factor = []
    tmp = int(n ** 0.5) + 1
    for num in range(2, tmp):
        while n % num == 0:
            n //= num
            factor.append(num)

    if n > 1:
        factor.append(n)

    return factor

#繰り返し２乗法
def modPow(a, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        halfP = p // 2
        half = modPow(a, halfP)
        return half * half % mod
    else:
        return a * modPow(a, p-1) % mod

#組み合わせ
def comb(a, b):
    if b > a - b:
        return comb(a, a-b)
    ansMul = 1
    ansDiv = 1
    for i in range(b):
        ansMul *= a - i
        ansDiv *= i + 1
        ansMul %= mod
        ansDiv %= mod

    ans = ansMul * modPow(ansDiv, mod-2) % mod
    return ans

#UnionFind
class UnionFind():

    def __init__(self, n):
        self.n = n
        self.root = [-1] * (n+1)

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

    def Unite(self, x, y):
        x = self.FindRoot(x)
        y = self.FindRoot(y)

        if x == y:
            return False
        if self.Size(x) < self.Size(y):
            x, y = y, x
        self.root[x] += self.root[y]
        self.root[y] = x

        return True

    def isSameGroup(self, x, y):
        return self.FindRoot(x) == self.FindRoot(y)

    def Size(self, x):
        return -self.root[self.FindRoot(x)]

N, M = map(int, input().split())
X = [0] * M
Y = [0] * M
Z = [0] * M
for i in range(M):
    X[i], Y[i], Z[i] = map(int, input().split())

Uni = UnionFind(N)

for i in range(M):
    Uni.Unite(X[i], Y[i])

roots = set()
for i in range(1, N+1):
    roots.add(Uni.FindRoot(i))

print(len(roots))


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

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef unordered_set<ll> uset;
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=0;i<=n;i++)
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define all(x) x.begin(),x.end()
#pragma gcc optimize("O3")
#pragma gcc optimize("unroll-loops")
#pragma gcc target("avx2,see4")

int main(){
	long double a,b,c;
	cin>>a>>b>>c;
	long double d=(long double)sqrt(a*b);
	if(a+b+2*d<c)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0; i<n; i++)
typedef long long ll;
typedef long long unsigned int llu;
ll MOD = 1000000007;
ll INF = 1000000009;



void solve(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    bool b = true;
    if(n%2==1) b = false;
    else{
        rep(i,n/2){
            if(s[i]!=s[i+n/2]) b = false;
        }
    }
    if(b) cout << "Yes" << endl;
    else cout << "No" << endl;
}

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


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

#ifdef LOCAL
#define debug(var) cerr << #var << " = " << var << endl;
#else
#define debug(var)
#endif

void init() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
}

void solve() {
	int n; scanf("%d", &n);
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		int l, r; scanf("%d%d", &l, &r);
		ans += r-l+1;
	}
	printf("%d", ans);
}

int main() {
	init();
	int t = 1; //scanf("%d", &t);
	while (t--) {
		solve();
	}
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<utility>
#include<set>
#include<complex>
#include<map>
#define vi vector<int>
#define vvi vector<vector<int> >
#define ll long long int
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vc vector<char>
#define vs vector<string>
#define ld long double
#define INF 1e9
#define EPS 0.0000000001
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define CC puts("-------ok--------");
#define all(in) in.begin(), in.end()
using namespace std;
typedef pair<int, int> pii;
typedef pair<int,string>psi;
#define MAX 99999999
int main(){
    int n;
    while(scanf("%d",&n),n){
        char c; scanf("%c",&c);
        vector<string>v(n+1);
        rep(i,n)getline(cin,v[i]);
        map<string,int>mp;
        vector<psi>aoa;
        rep(i,n){
            string temp="";
            rep(j,v[i].size()+1){
                if(v[i][j]==' '||v[i][j]=='\0'){mp[temp]++;temp.clear();}
                else temp.push_back(v[i][j]);
            }
        }
       // for(auto itr=mp.begin();itr!=mp.end();itr++)cout<<"key :"<<itr->first<<" value :"<<itr->second<<endl;
        char key; cin>>key;
        int poge=0;
        bool check=false;
        auto itr=mp.begin();
        for(;itr!=mp.end();itr++){
            if((itr->first)[0]==key){aoa.push_back(psi((-1)*(itr->second),itr->first));check=true;}
        }
        if(!check){cout<<"NA"<<endl; goto L;}
        sort(all(aoa));
        rep(i,aoa.size()){if(i)cout<<" ";cout<<aoa[i].second;poge++; if(poge==5)break;}
        cout<<endl;
    L:;
        }
    }

Measured memory_bytes: 3228
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string>
#include <limits>
#include <algorithm>
#include <map>
#include <sstream>
#include <unordered_map>

using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
static ull tenq = 1000000000;
static ull mod = tenq + 7;

using namespace std;

int main()
{
  ll N, M;
  cin >> N >> M;
  vector<pair<pair<ll, ll>, ll>> cities;
  for (ll i = 0; i < M; i++){
    ll p, y;
    cin >> p >> y;
    cities.push_back(make_pair(make_pair(p, y), i));
//    cities[i] = make_pair(p, y);
  }
  sort(cities.begin(), cities.end());
  vector<pair<ll, string>> res(M);
  ll count = 0;
  ll prev = -1;
  for (auto i = 0; i < M; i++) {
    string p = to_string(cities[i].first.first);
    if (cities[i].first.first != prev) count = 0;
    count++;
    prev = cities[i].first.first;
    string x = to_string(count);
    for (auto j = p.size(); j < 6; j++) p = "0" + p;
    for (auto j = x.size(); j < 6; j++) x = "0" + x;
//    res.emplace_back(make_pair(res[i].second, p + x));
//    res.push_back(make_pair(res[i].second, p + x));
    res[i] = make_pair(cities[i].second, p + x);
  }
  sort(res.begin(), res.end());

  for (auto i = 0; i < res.size(); i++) {
    cout << res[i].second << endl;
  }

  return 0;
}


Measured memory_bytes: 8688
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 5e5+7;
int main()
{
	int n, h, w;
	scanf("%d%d%d", &n, &h, &w);
	printf("%d\n", (n-h+1)*(n-w+1));
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int f(int a,int b,int c)
{
	if(a+b>c)
		return 1;
	return 0;
}
int main()
{
	#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin>>n;
	set<int> s;
	map<int,int> m;
	int i;
	int x;
	for(i=0;i<n;i++)
	{
		cin>>x;
		s.insert(x);
		m[x]++;
	}
	long long int ans=0;
	for(auto p=s.begin();p!=s.end();p++)
	{
		auto q=p,r=p;
		q++;
		for(;q!=s.end();q++)
		{
			r=q;
			r++;
			for(;r!=s.end();r++)
			{
				if(f(*p,*q,*r))
					ans+=m[*p]*m[*q]*m[*r];
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3664
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include <iomanip>
using namespace std;

int main(){
	int n,a=0,b=1,f=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=33;j++){
			b=j;
			for(int k=0;k<10;k++){
				b=b*j;
				if(b==i){
					a=i;
					break;
				}
				
			}
		}
		
		
	}
	cout<<a<<endl;
    return 0;
}

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

const ll infll=9223372036854775806;
const int inf=2147483646;

int main()
{
	//freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
	ios_base::sync_with_stdio(false); cin.tie(0);
	ld i,j,k,n,t,ans=0;
	string a;
	cin>>n;
	for (i=0;i<n;i++){
		cin>>t>>a;
		if (a[0]=='J'){
			ans+=t;
		}
		else {
			ans+=t*380000;
		}
	}
	cout.precision(18);
	cout<<ans;
	return 0;
}

Measured memory_bytes: 256
/*{{{*/
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <unordered_map>
#include <unordered_set>
#include <cassert>
using namespace std;
typedef pair<int, int> PP;
typedef long long LL;
#define pb push_back
#define fr first
#define sc second
#define bitcnt __builtin_popcount
#define all(x) x.begin(), x.end()
inline LL ri() {LL x; scanf("%lld", &x); return x;}
#define rep2(i, n, ...) for (int i = 0; i < (n); i ++) 
#define rep3(i, a, b, ...) for (int i = (a); i < (b); i ++)
#define GET_MACRO(_1, _2, _3, NAME, ...) NAME
#define rep(...) GET_MACRO(__VA_ARGS__, rep3, rep2)(__VA_ARGS__)
#define drep2(i, n, ...) for (int i = (n) - 1; i >= 0; i --)
#define drep3(i, a, b) for (int i = (a) - 1; i >= (b); i --)
#define drep(...) GET_MACRO(__VA_ARGS__, drep3, drep2)(__VA_ARGS__)
template<typename T>inline bool smax(T&a, T b){if(a<b){a=b;return true;}return false;} 
template<typename T>inline bool smin(T&a, T b){if(a>b){a=b;return true;}return false;} 
/*}}}*/



map<int, int> c;
int getRoot(int x)  {
  for (int i = 30; i >= 0; i --) {
    if (1 & (x >> i)) {
      return (1 << i);
    }
  }
  assert(false);
}

int getPw(int x) {
  int c = 0;
  while (x % 2 == 0) c ++, x >>= 1;
  return c;
}

//unordered_map<int, vector<int>> m;
//unordered_map<int, int> m[30];

unordered_map<int, int> m;

int a[2 * 100001], r[2 * 100001], p[2 * 100001];
int main() {
  int n;
  cin >> n;
  rep(i, n) cin >> a[i];
  sort(a, a + n);
  rep(i, n) {
    m[a[i]] ++;
  }
  
  int res = 0;
  drep(i, n) {
    if (!m[a[i]]) {
      continue;
    }
    //cout << a[i] << endl;
    m[a[i]] --;
    r[i] = getRoot(a[i]);
    int b = 2 * r[i] - a[i];
    if (m[b]) {
      m[b] --;
      res ++;
    }
  }
  cout << res << endl;


  return 0;
}


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

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

    int count_A = 0;

    for (auto c : s) {
        if (c == 'A') count_A++;
    }

    std::cout << (count_A == 0 || count_A == 3 ? "No" : "Yes");


    return 0;
}

Measured memory_bytes: 256
use std::cmp::*;
use std::io::*;
use std::str::FromStr;
use utils::*;

pub fn main() {
    let i = stdin();
    let mut o = Vec::new();
    run(i.lock(), &mut o);
    stdout().write_all(&o).unwrap();
}

fn run<R: BufRead, W: Write>(i: R, o: &mut W) {
    let mut i = CpReader::new(i);
    let n = i.read::<usize>();
    let mut a = Vec::new();
    for _ in 0..n {
        a.push(i.read::<isize>());
    }

    writeln!(o, "{}", solve(a)).unwrap();
}
fn solve(mut a: Vec<isize>) -> isize {
    a.sort();

    let v = a[0];
    let mut v = (v, v);
    let mut i = (1, a.len() - 1);

    let mut result = 0;

    while i.0 <= i.1 {
        let d = ((v.0 - a[i.1]).abs(), (v.1 - a[i.0]).abs());

        if d.0 >= d.1 {
            v.0 = a[i.1];
            i.1 -= 1;
            result += d.0;
        } else {
            v.1 = a[i.0];
            i.0 += 1;
            result += d.1;
        }
        v = (min(v.0, v.1), max(v.0, v.1));
    }
    result
}

mod utils {
    use super::*;

    pub struct CpReader<R: BufRead> {
        r: R,
        s: String,
    }

    macro_rules! fn_read {
        { $f:ident($($t:ident),*) } => {
            #[allow(dead_code)]
            pub fn $f<$($t: FromStr),*>(&mut self) -> ($($t),*) {
                let i = &mut self.read_line().split(' ');
                ($(read_next::<$t,_>(i)),*)
            }
        };
    }

    impl<R: BufRead> CpReader<R> {
        pub fn new(r: R) -> Self {
            CpReader {
                r: r,
                s: String::new(),
            }
        }
        pub fn read_line(&mut self) -> &str {
            self.s.clear();
            self.r.read_line(&mut self.s).unwrap();
            self.s.trim()
        }

        pub fn read<T: FromStr>(&mut self) -> T {
            self.read_line().parse().ok().unwrap()
        }
        fn_read! { read2(T1, T2) }
        fn_read! { read3(T1, T2, T3) }
        fn_read! { read4(T1, T2, T3, T4) }
        fn_read! { read5(T1, T2, T3, T4, T5) }
    }
    fn read_next<'a, T: FromStr, I: Iterator<Item = &'a str>>(i: &mut I) -> T {
        i.next().unwrap().parse().ok().unwrap()
    }

}


Measured memory_bytes: 6396
#include<algorithm>
#include<bits/allocator.h>
#include<bits/basic_ios.h>
#include<bits/basic_string.h>
#include<bits/basic_string.tcc>
#include<bits/c++config.h>
#include<bits/char_traits.h>
#include<bits/cpp_type_traits.h>
#include<bits/cxxabi_forced.h>
#include<bits/ios_base.h>
#include<bits/locale_classes.h>
#include<bits/localefwd.h>
#include<bits/ostream_insert.h>
#include<bits/postypes.h>
#include<bits/range_access.h>
#include<bits/stl_algobase.h>
#include<bits/stl_function.h>
#include<bits/stl_iterator.h>
#include<bits/stl_iterator_base_funcs.h>
#include<bits/stl_iterator_base_types.h>
#include<bits/stringfwd.h>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<cmath>
#include<complex>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cwchar>
#include<cwchar>
#include<cwctype>
#include<debug/debug.h>
#include<deque>
#include<exception>
#include<ext/atomicity.h>
#include<ext/numeric_traits.h>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<math.h>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<utility>
#include<valarray>
#include<vector>
using namespace std;
int a[100010];
int main()
{
	int k;
	cin>>k;
	queue<int> q;
	for (int i=0;i<100010;i++) a[i]=1e9;
	a[1]=1;
	q.push(1);
	while (!q.empty()){
		int x=q.front();q.pop();
		if (a[(x+1)%k]>a[x]+1){
			q.push((x+1)%k);
			a[(x+1)%k]=a[x]+1;
		}
		if (a[(x*10)%k]>a[x]){
			q.push((x*10)%k);
			a[(x*10)%k]=a[x];
		}
	}
	cout<<a[0]; 
	return 0;
}

Measured memory_bytes: 768
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

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

ll d[105][105];
int to[105][105];

void warshall_floyd(int n, int m) {
	rep(i, n) rep(j, n) d[i][j] = INF;
	rep(i, n) d[i][i] = 0;

	rep(i, n) rep(j, n) to[i][j] = j;

	//input
	rep(i, m) {
		int a, b, c;
		cin >> a >> b >> c;

		a--; b--;
		d[a][b] = c;
		// d[b][a] = c;
	}

	rep(k,n) {
		rep(i,n) {
			rep(j,n) {
				if(d[i][k] == INF || d[k][j] == INF) continue;
				if(d[i][j] > d[i][k] + d[k][j]) {
					d[i][j] = d[i][k] + d[k][j];
					to[i][j] = to[i][k];
				}
			}
		}
	}
}

vector<int> path(int s, int g) {
	int cur = s;
	vector<int> ret;
	for(; cur != g; cur = to[cur][g]) {
		ret.push_back(cur);
	}

	ret.push_back(g);
	return ret;
}

int main() {
	int n, m, s, g1, g2;
	while(cin >> n >> m >> s >> g1 >> g2) {
		if(n == 0 && m == 0 && s == 0 && g1 == 0 && g2 == 0) break;

		s--; g1--; g2--;
		warshall_floyd(n, m);

		ll ans = INF;
		rep(i, n) {
			ans = min(ans, d[s][i] + d[i][g1] + d[i][g2]);
		}

		ans = min(ans, d[s][g1] + d[g1][g2]);
		ans = min(ans, d[s][g2] + d[g2][g1]);

		cout << ans << endl;
	}

	return 0;
}

Measured memory_bytes: 1284
#include<algorithm>
#include<bitset>
#include<cmath>
#include<complex>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<iterator>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>
#include<chrono>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,x,n) for(int i=x; i<(n); i++)
#define vint(a,n) vint a(n); rep(i, n) cin >> a[i];
#define vll(a,n) vll a(n); rep(i, n) cin >> a[i];
#define ALL(n) begin(n),end(n)
#define RALL(n) rbegin(n),rend(n)
#define MOD (1000000007)
#define INF (2e9)
#define INFL (2e18)

typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
using vint=vector<int>;
using vll=vector<ll>;
using vbool=vector<bool>;
template<class T>using arr=vector<vector<T>>;
template<class T>int popcount(T &a){int c=0; rep(i, 8*(int)sizeof(a)){if((a>>i)&1) c++;} return c;}
template<class T>void pr(T x){cout << x << endl;}
template<class T>void prvec(vector<T>& a){rep(i, a.size()-1){cout << a[i] << " ";} pr(a[a.size()-1]);}
template<class T>void prarr(arr<T>& a){rep(i, a.size()) if(a[i].empty()) pr(""); else prvec(a[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; }

int main()
{
    int n; cin >> n;
    // vint a(n+1);
    ll ans = 0;
    int d = 0;
    for(ll a = 1; a < n; a++){
        for(ll b = a; a*b < n; b++){
            // pr(a*b);
            if(a==b) ans++;
            else ans += 2;
        }
    }
    pr(ans);
    return 0;}

Measured memory_bytes: 3636
#include <iostream>
#include <sstream>
#include <vector>

using namespace std;

int getcom(int x, int y) {
	int no = 2;

	while (true) {
		if (no > x || no > y) {
			return 1;
		}

		if (x % no == 0 && y % no == 0) {
			x = x / no;
			y = y / no;
			return no * getcom(x, y);
		}
		no++;
	}
}

int main(void) {
	int a, b;

	vector<string> v;
	while (cin >> a >> b) {
		int com_div, com_mlt;

		com_div = getcom(a, b);
		com_mlt = (a / com_div) * (b / com_div) * com_div;
		stringstream ss;
		ss << com_div << " " << com_mlt;
		v.push_back(ss.str());
	}

	for (int i = 0; i < v.size(); i++) {
		cout << v[i] << endl;
	}

	return 0;
}

Measured memory_bytes: 3012
MOD = 10**9+7
s = gets.chomp.split("")
len = s.length
num = Array.new(len+1).map{Array.new(13,0)}

num[0][0] = 1

for i in 0..len-1
  tmp = Array.new(13,0)
  tmp2 = num[i]
  if s[i] == "?"
    13.times do |k|
      #やけくそ
      tmp[(k*10)%13] += tmp2[k]
      tmp[(k*10+1)%13] += tmp2[k]
      tmp[(k*10+2)%13] += tmp2[k]
      tmp[(k*10+3)%13] += tmp2[k]
      tmp[(k*10+4)%13] += tmp2[k]
      tmp[(k*10+5)%13] += tmp2[k]
      tmp[(k*10+6)%13] += tmp2[k]
      tmp[(k*10+7)%13] += tmp2[k]
      tmp[(k*10+8)%13] += tmp2[k]
      tmp[(k*10+9)%13] += tmp2[k]
    end
  else
    j = s[i].to_i
    13.times do |k|
      tmp[(k*10+j)%13] += tmp2[k]
    end
  end
  13.times do |k|
    tmp[k] %= MOD
  end
  num[i+1] = tmp
end

puts num[len][5]

Measured memory_bytes: 36604
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;}
const ll INF = 1LL<<60;
/*template*/

ll p[8]={0},q[8]={0};

ll func(ll x){
  ll res=1;
  for(ll i=2;i<=x;i++)res*=i;
  return res;
}

int main()
{
  ll n;cin>>n;
  ll hoge;
  for(ll i=0;i<n;i++){
    cin>>hoge;p[i]=hoge-1;
  }
  for(ll i=0;i<n;i++){
    cin>>hoge;q[i]=hoge-1;
  }
  ll a=0,b=0;
  for(ll i=0;i<n;i++){
    a+=func(n-1-i)*p[i];
    b+=func(n-1-i)*q[i];
    for(ll j=i+1;j<n;j++){
      if(p[j]>p[i])p[j]--;
      if(q[j]>q[i])q[j]--;
    }
  }
  ll ans= a>b ? a-b:b-a;
  cout<<ans<<endl;

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#define swap(type ,a ,b) {type t; t=a; a=b; b=t;}
#define forN(i,n) for(i=0;i<n;i++)
#define forR(i,s,n) for(i=s;i<n;i++)
#define ll long long
#define pb(t,d,n) {t p;int i;forN(i,n){cin>>p;d.push_back(p);}}

using namespace std;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> pii;
typedef vector<pair<int,int>> vpii;

bool cmp(pii &a, pii &b){
    return a.first < b.first;
}

int main(){
    int i,n,m,ta,tb;
    ll res;
    vpii d;
    cin >> n >> m;
    forN(i,n){
        cin >> ta >> tb;
        d.push_back({ta,tb});
    }
    res = 0;
    sort(d.begin(), d.end(), cmp);
    forN(i,n){
        if(m - d[i].second > 0){
            m -= d[i].second;
            res += d[i].first * d[i].second;
        }
        else{
            res += d[i].first * m;
            break;
        }
    }
    cout << res << endl;
}

Measured memory_bytes: 1400
fun main(args: Array<String>) {
    abc118c()
}

fun abc118c() {
    val n = readLine()!!.toInt()
    val aList = readLine()!!.split(" ").map { it.toLong() }

    val answer = aList.reduce { acc, l -> gcd(acc, l) }

    println(answer)
}

private tailrec fun gcd(a: Long, b: Long): Long {
    return if (b == 0L) a else gcd(b, a % b)
}


Measured memory_bytes: 57764
from collections import Counter

class hashabledict(dict):
    def __hash__(self):
        return hash(tuple(sorted(self.items())))

N = int(input())
words = [hashabledict(dict(Counter(input()))) for _ in range(N)]
ans = 0
counter_hash = {}
for counter in words:
    if counter not in counter_hash.keys():
        counter_hash[counter] = 1
    else:
        counter_hash[counter] += 1
 
for count in counter_hash.values():
    ans += int((count * (count-1)) / 2)
print(ans)

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

int main(){
	int N;
	string S;
	cin >> N >> S;
	int l = S.size();

	for(int i=0;i<l;i++){
		cout << char( (N + S[i] - 'A')%26 +'A' );
	}
	cout <<endl;

	//cout << char('a'+0) <<endl;
	/*cout << 'a' <<endl;
	cout << 'a' + 0 <<endl;

	cout << 97 <<endl;
	cout << 'b' - 'a' <<endl;

    cout << char(97) <<endl;*/
  	return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<vector>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
using ll = long long;
using P = pair<int, int>;
#include<algorithm>
#include<math.h>
#include<map>
#include<queue>

int main() {
	int s;
	cin >> s;
	int a[3];
	rep(i, 3) {
		int p=s % 10;
		a[i] = p;
		s /=10;
		//cout << s << endl;
	}
	rep(i, 3) {
		//cout << a[i];
		if (a[i] == 7) {
			cout << "Yes";
			return 0;
		}
	}
	cout << "No";
	return 0;
}

Measured memory_bytes: 3592
h,w,d=map(int,input().split())
l={}
for i in range(h):
  l1=list(map(int,input().split()))
  for j in l1:
    l[j]=[l1.index(j)+1,i+1]
li=[]
for i in range(1,d+1):
  l11=[]
  c=0
  x=l[i][0]
  y=l[i][1]
  while i<=h*w:
    c+=abs(x-l[i][0])+abs(y-l[i][1])
    l11.append(c)
    x=l[i][0]
    y=l[i][1]
    i+=d
  li.append(l11)
q=int(input())
for i in range(q):
  a,b=map(int,input().split())
  r=a%d
  if r==0:
    print(li[d-1][b//d-1]-li[d-1][a//d-1])
  else:
    print(li[r-1][b//d]-li[r-1][a//d])

Measured memory_bytes: 34208
#include <stdio.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include <stdlib.h>
#include <sys/stat.h>
#include <string.h>


int N_all;
int D_dis;


int main(int argc, char* argv[]){
    int i,j;
    int xx,yy,count;
    double xx_d,yy_d,dd,d_set;
    count=0;
    scanf("%d %d",&N_all,&D_dis);
    d_set = D_dis*1.;
    for(i=1;i<=N_all;i++){
        scanf("%d %d",&xx,&yy);
        xx_d = xx*1.;
        yy_d = yy*1.;
        dd = sqrt(xx_d*xx_d + yy_d*yy_d);
        if( dd <= d_set ){
            count++;
        }
    }
    printf("%d",count);
    return 0;
}

Measured memory_bytes: 2152
#include <algorithm>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <vector>

using namespace std;

#define rep(i, n) for (int64_t i = 0; i < (int64_t)(n); i++)
#define irep(i, n) for (int64_t i = 0; i <= (int64_t)(n); i++)
#define rrep(i, n) for (int64_t i = (n)-1; i >= 0; i--)
#define rirep(i, n) for (int64_t i = n; i >= 0; i--)

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

  int result = 0;
  rep(i, N - 1) {
    if (a[i] == a[i + 1]) {
      a[i + 1] = 0;
      result++;
    }
  }
  cout << result << endl;
  return 0;
}

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

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

const double PI = acos(-1);
const int inf = 2e9;
const ll INF = 2e18;
const ll MOD = 1e9+7;

#define sz(s) (s).size()
#define pb push_back
#define fi first
#define se second
#define REP(i,n) for (int i = 0; i<n; i++)
#define ALL(a) begin(a), end(a)

int main (void) {
  ll D,G;
  cin>>D>>G;
  vector<pair<int,int>> q(D);
  REP(i,D) {
    cin>>q[i].fi>>q[i].se;
  }
  ll ans = INF;
  REP(i,(1<<D)) {
    vector<int> used(D,false);
    int t = i;
    ll num = 0;
    ll point = 0; 
    REP(j,D) {
      if (t%2 == 0) {
        used[j] = true;
        num += q[j].fi;
        point += q[j].fi * (j+1) * 100 + q[j].se;
      }
      t /= 2;
    }
    if (point >= G) {
      ans = min(ans,num);
    }
    else {
      for (int j=D-1;j>=0;j--) {
        if (used[j]) continue;
        if (G - point < q[j].fi * (j+1) * 100) {
          ll d = (G - point) / ((j+1)*100);
          num += d;
          point += d * (j+1) * 100;
          ans = min(ans,num);
          break;
        }
        else {
          break;
        }
      }
    }
  }
  if (ans==0) ans = 1;
  cout<<ans<<endl;
  return 0;
}

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

public class Main{
  public static void main(String[] args)throws Exception{
    Scanner sc = new Scanner(System.in);
    int[] arr = {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
};
    int N = sc.nextInt()-1;
    System.out.println(arr[N]);
  }
}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
#include <sys/types.h>
#include <unistd.h>

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

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

using ll=long long;
using R=long double;
const R EPS=1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r){return(r > EPS)-(r < -EPS);}
inline R sq(R x){return sqrt(max(x,0.0L));}

const int dx[8]={1,0,-1,0,1,-1,-1,1};
const int dy[8]={0,1,0,-1,1,1,-1,-1};

const pid_t pid = getpid();
// Problem Specific Parameter:

int main(void){
	string s;
	cin >> s;
	const string keyence = "keyence";

	const int n = s.size();
	bool ok = false;
	
	rep(l,n+1)rep(r,n+1){
		if(l > r) continue;
		string cur ="";
		rep(i,n){
			if(l <= i and i < r) continue;
			cur += s[i];
		}
		if(cur == keyence) ok = true;
	}

	puts(ok?"YES":"NO");
	return 0;
}

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

int main()
{
  priority_queue<int> a;
  int N;
  int temp;
  int A_sum = 0;
  int B_sum = 0;

  cin >> N;
  for (int i = 0; i < N; i++)
  {
    cin >> temp;
    a.push(temp);
  }
  for (int i = 0; i < N / 2; i++)
  {
    A_sum += a.top();
    a.pop();
    B_sum += a.top();
    a.pop();
  }
  if (!a.empty())
    A_sum += a.top();
  cout << A_sum - B_sum << endl;
}

Measured memory_bytes: 256
N = int(input())
S = input()

nr = S.count("R")
ng = S.count("G")
nb = S.count("B")

exp = 0
for i in range(N-2):
    for d in range(1,(N-1-i)//2+1):
        if S[i] !=S[i+d] and S[i+d] != S[i+2*d] and S[i] != S[i+2*d]:
            exp = exp +1

print(nr*ng*nb-exp)

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

int main() {
  int H,A;
  cin >> H >>A;
  int count = 0;
  
  
  while(true) {
    H -= A;
    count++;
    
    if(H <=0) {
      break;
    }
  }
  cout << count <<endl;
  return 0;
}

Measured memory_bytes: 256
n=int(input())
A=[]
for i in range(n):
  a,b,c=map(int,input().split())
  if a<b+c or (b+c)%2!=a%2:
    print("No")
    exit()
  A.append([a,b,c])
if n==1:
  print("Yes")
  exit()
for i in range(n-1):
  if not A[i+1][0]-A[i][0]>=A[i+1][2]+A[i+1][1]-A[i][1]-A[i][2]:
    print("No")
    exit()
print("Yes")


Measured memory_bytes: 19504
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

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

		for(;;) {
			String num = br.readLine();
			String[] set = num.split(" ");

			int a = Integer.parseInt(set[0]);
			int b = Integer.parseInt(set[1]);

			if (a == 0 && b == 0) {
				break;
			} else if (a > b) {
			sb.append(b).append(" ").append(a).append("\n");
			} else {
			sb.append(a).append(" ").append(b).append("\n");
			}
		}

		System.out.print(sb);

	}
}

Measured memory_bytes: 26240
#include <iostream>
#include <algorithm>
#include <string>
#include <map>
#include <vector>
#define ll long long 
using namespace std;

int main() {
	int n,m, A, sum = 0, ans=0;
	int a[100];
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		sum += a[i];
	}
	A = sum / n;
	if ((double)sum / n > (double)A + 0.5) {
		m = A + 1;
	} else {
		m = A;
	}
	for (int i = 0; i < n; i++) {
		ans += (a[i] - m)*(a[i] - m);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
# include <cstdio>
# include <iostream>
# include <vector>
# include <map>
# include <set> 
# include <algorithm> 
# include <string>
# include <cstring>
# include <queue> 
# include <stack> 
# include <cstdlib> 

using namespace std ; 

const long long factor = 1000000000LL ; 

long long labs(long long a)
{
	if(a<0LL) return -a; 
	return a; 
}

long long minVal(long long a, long long b)
{
	if(a<b) return a ; 
	return b ;
}

long long maxVal(long long a, long long b)
{
	if(a>b)return a ; 
	return b; 
}

void scale(long long &a, long long &b)
{
	long long minV = minVal(a,b), maxV = maxVal(a, b);
	if(minV <0)
	{
		if(minV == a)
		{
			a = minV + factor ; 
			b = maxV + factor ; 

		}
		else{
			a = maxV + factor ; 
			b = minV + factor ; 
		} 
	}
	else return ; 
}


int main()
{
	long long A, B, V, W, T ; 
	cin >> A >> V >> B >> W >> T ; 
	
	//scale(A,B) ; 

	// if(A<0)
	// {
	// 	A += factor ; 
	// 	B += factor ; 
	// }
	// if(B<0)
	// {
	// 	A += factor ; 
	// 	B += factor ; 
	// }

	int abDistance = labs(A-B) ; 

	if(V*T >= abDistance + (W*T)) cout << "YES\n";
	else cout << "NO\n";


	// if( A + (V*T) >= B+ (W*T)) cout << "YES\n";
	// else cout << "NO\n"; 

	
	return 0 ; 
}

Measured memory_bytes: 3092
#include <iostream>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <limits>
#include <algorithm>
#include <functional>

using namespace std;

namespace string_helper
{
	bool check_palindrome(const string& word)
	{
		if (word.empty()) return true;

		size_t lo = 0;
		size_t hi = word.size() - 1;

		while (lo < hi)
		{
			if (word[lo] != word[hi]) return false;

			lo++;
			hi--;
		}

		return true;
	}
}

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

	string S;
	cin >> S;

	if (string_helper::check_palindrome(S))
	{
		string S2 = S.substr(0, (S.size() - 1) / 2);
		string S3 = S.substr(((S.size() + 3) / 2) - 1, (S.size() - 1) / 2);

		if (string_helper::check_palindrome(S2) && string_helper::check_palindrome(S3))
		{
			cout << "Yes";
			return 0;
		}
	}

	cout << "No";

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
using namespace std;
int main() {
    int n;
    cin>>n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++)
        cin>>arr[i];
    int ctr = 0, mx = 0;
    for (int i = 0; i < n - 1; i++) {
        if (arr[i + 1] <= arr[i]) {
            ctr++;
        }
        else {
            mx = max(mx, ctr);
            ctr = 0;
        }
    }
    mx = max(mx, ctr);
    cout<<mx;
}


Measured memory_bytes: 640
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, m = map(int, readline().split())
    if m % 2 == 0:
        rem = m
        for i in range(m // 2):
            print(i + 1, m + 1 - i)
            rem -= 1
            if rem == 0:
                return
        for i in range(n):
            print(m + 2 + i, 2 * m + 1 - i)
            rem -= 1
            if rem == 0:
                return
    else:
        rem = m
        for i in range((m - 1) // 2):
            print(i + 1, m - i)
            rem -= 1
            if rem == 0:
                return
        for i in range(n):
            print(m + 1 + i, 2 * m + 1 - i)
            rem -= 1
            if rem == 0:
                return


if __name__ == '__main__':
    main()


Measured memory_bytes: 75940
// https://atcoder.jp/contests/abc018/tasks/abc018_4

#include <bits/stdc++.h>
using namespace std;
#define REP1(i,n) for(int i=1, i##_len=(n); i<i##_len; ++i)
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define pow(x) x*x
#define ll long long
static const int MAX = 10000;
static const ll INFTY = 1e18;
static const ll MOD = 1e9 + 7;

struct edge {
    ll to, cost;
};

using Graph = vector<vector<int>>;
using _Graph = vector<vector<edge>>;
// 入力
// int H, W;
vector<vector<char>> field;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

// 深さ優先探索
vector<bool> seen;
vector<int> colors;

int main() {

  int N;
  cin >> N;
  vector<ll> A(N);
  REP(i, N){
    cin >> A[i];
  }

  ll ans = 0;

  REP(i, 61){
    ll num1 = 0;
    ll num0 = 0;
    REP(j, N){
      // ll keta = 1LL < i;
      if((A[j] >> i) & 1LL) num1++;
      else num0++;
    }
    ll keta = 1LL << i;
    keta %= MOD;
    ll tmp = keta * num1;
    tmp %= MOD;
    tmp =  tmp * num0;
    tmp %= MOD;
    ans += tmp;
    ans %= MOD;
  }
  ans %= MOD;

  cout << ans << endl;


  return 0;

}
/*
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
         pass System Test!
*/

Measured memory_bytes: 2560
#include<stdio.h>

int main(){
	int l,i=0;
	double m,n;
	while(scanf("%d,%lf,%lf",&l,&m,&n)!=EOF){
		if(25.0<=m/(n*n)){printf("%d\n",l);i++;}
	}
	if(i==0)printf("????????????\n");
		return 0;
}

Measured memory_bytes: 1056
#include <stdio.h>

int main(){
  int n,t,i,tmp;
  int start=0,time=0,count=0;
  
  scanf("%d %d",&n,&t);
  
  for(i=0;i<n;i++){
    scanf("%d",&tmp);
    if(tmp<=time && i<n-1){
      time=tmp+t;
    } else if(tmp>time && i<n-1){
      count+=(time-start);
      start=tmp;
      time=tmp+t;
    } else if(tmp<=time && i==n-1){
      time=tmp+t;
      count+=(time-start);
    } else {
      count+=(time-start);
      count+=t;
    }
  }
  printf("%d",count);
}

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

int main() {
  int N; cin >> N;
  int A[N]; for (int i = 0; i < N; i++) cin >> A[i];
  int all_xor = 0; for (int i = 0; i < N; i++) all_xor ^= A[i];
  for (int i = 0; i < N; i++) {
    cout << (all_xor ^ A[i]);
    if (i == N - 1) cout << endl;
    else cout << " ";
  }
}

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

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

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

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

    return arr
fact = factorization(n)
cnt = 0

for i in range(len(fact)):
    for j in range(1,fact[i][1]+1):
        if n==1:
            print(cnt)
            exit()
        if n%(fact[i][0]**j)==0:
            cnt += 1
            n = n/(fact[i][0]**j)
print(cnt)




Measured memory_bytes: 9416
from collections import deque
def resolve():
    INF = 1 << 60
    H, W = map(int, input().split())
    G = [input() for _ in range(H)]

    dist = [[INF] * W for _ in range(H)]
    dist[0][0] = 0 if G[0][0] == "." else 1

    q = deque()
    q.append((dist[0][0], 0, 0))
    drc = [(1, 0), (0, 1)]
    while q:
        cost, y, x = q.popleft()
        for dy, dx in drc:
            ny = y + dy
            nx = x + dx
            if y + dy >= H or x + dx >= W:
                continue
            nx_cost = cost if G[y][x] == G[ny][nx] else cost + 1
            if nx_cost < dist[ny][nx]:
                dist[ny][nx] = nx_cost
                q.append((dist[ny][nx], ny, nx))

    ans = (dist[H - 1][W - 1] + 1) // 2
    print(ans)


if __name__ == "__main__":
    resolve()


Measured memory_bytes: 9568
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vin=vector<int>;
using vll=vector<long long>;
using vvin=vector<vector<int>>;
using vvll=vector<vector<long long>>;
using vstr=vector<string>;
using vvstr=vector<vector<string>>;
using vch=vector<char>;
using vvch=vector<vector<char>>;
using vbo=vector<bool>;
using vvbo=vector<vector<bool>>;
using vpii=vector<pair<int,int>>;
using pqsin=priority_queue<int,vector<int>,greater<int>>;
#define mp make_pair
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,s,n) for(int i=(s);i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define decp(n) cout<<fixed<<setprecision((int)n)
const int inf=1e9+7;
const ll INF=1e18;


vll d(100050);

void dijkstra(ll s,vector<vector<pair<ll,ll>>> edge){
    priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> q;
    fill(all(d),INF);
    d[s]=(ll)0;
    q.push(mp(0,s));
    while(q.size()){
        auto p=q.top();q.pop();
        auto v=p.second;
        if(d[v]<p.first)continue;
        for(auto e:edge[v]){
            if(d[e.first]>d[v]+e.second){
                d[e.first]=d[v]+e.second;
                q.push(mp(d[e.first],e.first));
            }
        }
    }
}

int x,y,di,c;
ll tmp;
vin p(25);
vll q(60),r(60);
vvll dist(105,vll(105));
vll cost(200050);

ll train(int n,int m,int co,int s,int g){
    vector<vector<pair<ll,ll>>> edge(100050);
    vector<vector<tuple<int,int,int>>> ed(25);
    rep(i,m){
        cin>>x>>y>>di>>c;
        ed[c-1].push_back(make_tuple(x,y,di));
    }
    rep(i,co)cin>>p[i];
    rep(i,co){
        fill(all(q),(ll)0);fill(all(r),(ll)0);
        q[p[i]]=200030;
        rep(j,p[i]-1)cin>>q[j+1];
        rep(j,p[i])cin>>r[j];
        rep(j,n+1)rep(k,n+1){
            if(j==k)dist[j][k]=0;
            else dist[j][k]=INF;
        }
        for(auto e:ed[i]){
            tmp=get<2>(e);
            dist[get<0>(e)][get<1>(e)]=min(dist[get<0>(e)][get<1>(e)],tmp);
            dist[get<1>(e)][get<0>(e)]=min(dist[get<1>(e)][get<0>(e)],tmp);
        }
        rep2(j,1,n+1)rep2(k,1,n+1)rep2(l,1,n+1)dist[k][l]=min(dist[k][l],dist[k][j]+dist[j][l]);
        fill(all(cost),(ll)0);
        rep(j,p[i]){
            rep2(k,q[j],q[j+1])cost[k+1]=cost[k]+r[j];
        }
        rep2(j,1,n+1)rep2(k,1,n+1){
            if(j==k||dist[j][k]==INF)continue;
            edge[j].push_back(mp(k,cost[dist[j][k]]));
        }
    }
    //rep2(i,1,n)cout<<cost[i]<<" ";cout<<endl;
    /*rep2(i,1,n+1){
        for(auto tmp:edge[i])cout<<tmp.first<<" ";
        cout<<endl;
    }*/
    /*rep2(i,1,n+1){
        rep2(j,1,n+1)cout<<dist[i][j]<<" ";
        cout<<endl;
    }*/
    dijkstra(s,edge);
    //rep2(i,1,n)cout<<d[i]<<endl;
    if(d[g]==INF)return -1;
    return d[g];
}

int main(){
    int n,m,co,s,g;
    queue<ll> ans;
    while(1){
        cin>>n>>m>>co>>s>>g;
        if(n==0)break;
        ans.push(train(n,m,co,s,g));
    }
    while(ans.size()){
        cout<<ans.front()<<endl;
        ans.pop();
    }
}


Measured memory_bytes: 16488
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vin=vector<int>;
using vll=vector<long long>;
using vstr=vector<string>;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,s,n) for(int i=(s);i<(int)(n);i++)
#define _GLIBCXX_DEBUG
int main()
{
    int n;
    cin>>n;
    int d=0;
    int a=1;
    while(a<=n){
        a*=10;
        d++;
    }
    int sum=0;
    int b=1;
    int c=10;
    for(int i=1;i<d;i+=2){
        sum+=c-b;
        b*=100;
        c*=100;
    }
    if(d%2)sum+=n+1-a/10;
    cout<<sum<<endl;
}

Measured memory_bytes: 256
console.log((args=>{
  const S = args.trim();
  if ( /RRR/.test(S) ) return 3;
  if ( /RR/.test(S) ) return 2;
  if ( /R/.test(S) ) return 1;
  return 0;
})(require('fs').readFileSync('/dev/stdin','utf8')));


Measured memory_bytes: 29676
$<.map{|e|n,*a,d=e.split.map &:to_i;h={0=>0,1=>d};f=->x{h[x]||=a.zip([2,3,5]).map{|a,b|[x%b*d+f[x/b]+a,-x%b*d+f[0--x/b]+a,x*d].min}.min};d&&p(f[n])}

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

	int d;
	cin >> d;
	int c[26];
	int i, j;
	for (i = 0; i < 26; i++) {
		cin >> c[i];
	}
	int s[365][26];
	for (i = 0; i < d; i++) {
		for (j = 0; j < 26; j++) {
			cin >> s[i][j];
		}
	}
	int last[26];
	for (i = 0; i < 26; i++) {
		last[i] = 0;
	}
	int jmax, jindex;
	for (i = 1; i <= d; i++) {

		jmax = 0;
		jindex = -1;
		for (j = 0; j < 26; j++) {
			if (c[j] *(i - last[j]) > jmax) {
				jmax = c[j] *(i - last[j]);
				jindex = j;
			}
			else if (c[j] *(i - last[j]) == jmax) {
				if (s[i - 1][j] > s[i - 1][jindex]) {
					jindex = j;
				}
			}
		}
		for (j = 0; j < 26; j++) {
			if (s[i - 1][j] + 15 * c[j] * (i - last[j]) >= jmax) {
				jmax = s[i - 1][j] + 15 * c[j] * (i - last[j]);
				jindex = j;
			}
		}
		last[jindex] = i;
		cout << jindex + 1 << endl;
		


	}
	return 0;


}

Measured memory_bytes: 3676
#include <cstdio>
#include <cctype>
#include <utility>
#include <unordered_map>
using namespace std;

#define gcu getchar_unlocked
#define pcu putchar_unlocked
#define _T template <typename T>
#define _HT template <typename H, typename... T>
#define _il inline
#define _in _il int in
#define _sc _il bool scan
_T T in(int c){T n=0;bool m=false;while(isspace(c)){c=gcu();}if(c=='-')m=true,c=gcu();
	do{n=10*n+(c-'0'),c=gcu();}while(c>='0');return m?-n:n;} //&&c<='9'
_in() {return in<int>(gcu());}
_T T scan(T &n){int c=gcu();return c==EOF?false:(n=in<T>(c),true);}
_sc(char &c){c=gcu();gcu();return c!=EOF;}
#ifdef _GLIBCXX_STRING
_sc(string &s){int c;s="";
	for(;;){c=gcu();if(c=='\n'||c==' ')return true;else if(c==EOF)return false;s+=c;}}
#endif
_HT _sc(H &h, T&&... t){return scan(h)&&scan(t...);}
#define _vo _il void out
#define _vl _il void outl
_vo(bool b) {pcu('0'+b);}
_vo(const char *s){while(*s)pcu(*s++);}
_vo(char c){pcu(c);}
#ifdef _GLIBCXX_STRING
_vo(string s){for(char c:s)pcu(c);}
#endif
_T _vo(T n){static char buf[20];char *p=buf;
	if(n<0)pcu('-'),n*=-1;if(!n)*p++='0';else while(n)*p++=n%10+'0',n/=10;
	while (p!=buf)pcu(*--p);}
_vl(){out('\n');}
#ifdef _GLIBCXX_VECTOR
_T _vo(vector<T> &v){for(T &x:v)out(&x == &v[0]?"":" "),out(x);outl();}
#endif
_HT _vo(H&& h, T&&... t){out(h);out(move(t)...);}
template <typename... T> _vl(T&&... t){out(move(t)...);outl();}

int main() {
	for (int N, Q; N = in(), Q = in();) {
		unordered_map<int, int> u;
		int m = 0, D = 0;
		while (N--) {
			for (int M = in(); M; M--) {
				int d = in();
				u[d]++;
				if (u[d] >= Q)
					if (u[d] > m || (u[d] == m && d < D)) {
						m = u[d];
						D = d;
					}
			}
		}
		outl(D);
	}
}


Measured memory_bytes: 2420
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ll long long
#define ld long double
#define all(a) a.begin(),a.end()
#define endl '\n'
#define ull unsigned long long
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define iter vector<int>::iterator
#define iter1 vector<int>::iterator
#define int long long
using namespace std;
using namespace __gnu_pbds;

template<class T>
using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

template<class T>
using ordered_multiset=tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rnd1(chrono::steady_clock::now().time_since_epoch().count());

//find_by_order
//order_of_key

const int N=2e5+7;
const int inf=1e18+1e9;
const int mod=1e9+7;
const ld eps=1e-9;

int dp[N][3];
int a[N][3];

main ()
{
    ios;
    int n;
    cin>>n;
    for (int i=1;i<=n;++i){
        for (int j=0;j<3;++j){
            cin>>a[i][j];
        }
    }
    for (int i=1;i<=n;++i){
        for (int j=0;j<3;++j){
            int mx=0;
            for (int k=0;k<3;++k){
                if (k==j)continue;
                mx=max(mx,dp[i-1][k]);
            }
            dp[i][j]=mx+a[i][j];
        }
    }
    int ans=max(dp[n][0],dp[n][1]);
    ans=max(ans,dp[n][2]);
    cout<<ans<<endl;
}


Measured memory_bytes: 8448
#include <bits/stdc++.h>
//#define int long long
using namespace std;
const int pm=1000000007;

int H,W;
vector<string>field;

const int dx[4] ={1,0,-1,0};
const int dy[4]={0,1,0,-1};

// void bfs(int h,int w,vector<vector<bool>> &seen){
	// seen[h][w]=ture;
	

signed main(){
	int H,W;
	cin>>H>>W;
	field.assign(H,"");
	for(int i=0;i<H;i++)cin>>field[i];
	int ans=0;

	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			//i,jがはじめのスタート地点
			if(field[i][j]=='#')continue;
			vector<vector<int>> dist(H,vector<int>(W,-1));
			queue<pair<int,int>> que;
			dist[i][j]=0; que.push(make_pair(i,j));
			
			//ここからbfs開始
			while(!que.empty()){
				pair<int,int> ij;
				ij=que.front();
				que.pop();
				// cout<<ij.first<<' '<<ij.second<<endl;
				for(int dir=0;dir<4;dir++){
					int nh=ij.first+dx[dir];
					int nw=ij.second+dy[dir];
					if(nh<0 || nh>=H || nw<0 || nw>=W)continue;
					if(field[nh][nw]=='#')continue;
					
					if(dist[nh][nw]==-1){
						dist[nh][nw]= dist[ij.first][ij.second]+1;
						// cout<<dist[nh][nw]<<endl;
						if(ans<dist[nh][nw])ans=dist[nh][nw];
						que.push(make_pair(nh,nw));
					}
				}
			}
		}
	}
	
	
	cout<<ans<<endl;
	return 0;
	
}



Measured memory_bytes: 256