akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

#define IOS ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define AfterDecimal(n) cout << fixed << setprecision(n);
#define ll long long int
#define ld long double
#define all(a) a.begin(), a.end()
#define pii pair<int, int>
#define pll pair<ll, ll>
#define bits(x) __builtin_popcount(x)

using namespace __gnu_pbds;
using namespace std;

// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC optimization ("unroll-loops")

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

typedef tree<int, null_type, less<int>, rb_tree_tag,
            tree_order_statistics_node_update>
    ordered_set;

#ifdef LOCAL
#define debug(...) __f(#__VA_ARGS__, __VA_ARGS__)
template<typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cout << "# "<< name << " = " << arg1 << '\n';
}
template<typename Arg1, typename... Args>
void __f(const char* names, Arg1 && arg1, Args &&... args){
        const char* comma = strchr(names + 1 ,',');
        cout << "# ";
        cout.write(names, comma - names)<< " = " << arg1 << " | ";
        __f(comma + 1, args...);
}
#else
#define debug(...) 36
#endif


std::mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline int ri(int a, int b) {
    return uniform_int_distribution<int>(a, b)(rng);
}

ll power(ll x, ll y, ll p){
   ll res = 1;
   x = x % p;
   while (y > 0) {
      if (y & 1)
         res = (res * x) % p;
      y = y >> 1;
      x = (x * x) % p;
   }
   return res;
}

const ll INF = (ll)(8e18);
const ll MOD = (ll)(1e9 + 7);
const ll HMOD = (ll)4222234727;
const ll Hashprime = (ll)31;

const int maxn = 100100;

int32_t main(){
    IOS;
    #ifndef ONLINE_JUDGE
    //  freopen("input.txt", "r", stdin);
    //  freopen("output.txt", "w", stdout);
    #endif
    int TestCases = 1; // cin >> TestCases;
    while(TestCases--){
       int n,k; cin >> n >> k;
       int ans = 0;
       while(n > 0){
         n = n / k;
         ans += 1;
       }
       cout << ans << '\n';
    }
    #ifdef LOCAL
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
    #endif
}
//g++ -DLOCAL -std=c++17 -Wshadow -Wall -o "c" "comp.cpp" -fsanitize=address -fsanitize=undefined -D_GLIBCXX_DEBUG -g


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

int main(){
	string s = "";
	for(int i = 0; i < 4; i++){
		string t;
		cin >> t;
		s += t;
	}
	sort(s.begin(), s.end());
	if(s == "1479") cout << "YES" << endl;
	else cout << "NO" << endl;
}

Measured memory_bytes: 256
def insertionsort(A, n):
    for i in range(1, n):
        v = A[i]
        j = i - 1
        while j >= 0 and A[j] > v:
            A[j+1] = A[j]
            j -= 1
        A[j+1] = v
        prt(A)

def prt(A):
    for i in A:
        if i != A[len(A)-1]: print(i, end=" ")
        else: print(i)

n = int(input())
A = input().split()
A = [int(i) for i in A]
prt(A)
insertionsort(A, n)


Measured memory_bytes: 5976
#include <bits/stdc++.h>
#include <cstdio>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)

int main()
{
    string s;
    long ans = 0;
    long m = 1;
    long tmp = 0;
    long digit = 1;
    long cint;
    long p = 2019;
    vector<long> modlist(2019, 0);
    modlist.at(0)++;
    // scanf("%d", &x);
    cin >> s;
    // cout << s << endl;
    rep(i, s.length())
    {
        cint = s[s.length() - i - 1] - '0';
        tmp += cint * digit;
        tmp %= p;
        // l.push_back(tmp);
        // cout << tmp << " " << ans << endl;
        digit *= 10;
        digit %= p;

        ans += modlist[tmp];
        modlist[tmp]++;
        // cout << cint << endl;
    }
    cout << ans << endl;
    // printf("%d\n", x * x * x);
}

Measured memory_bytes: 3736
#include <iostream>
#include <vector>
#include <set>
#define int long long
using namespace std;

const int N = 200 * 1000 + 8, mod = 1000 * 1000 * 1000 + 7;
const long long inf = 1ll * N * mod;
int n, m;

vector <pair <int, long long> > adj[N];
long long dis1[N], dis2[N];
int dp1[N], dp2[N];
set <pair <long long, int> > s;

void dij(int st, long long dis[], int cnt[]) {
	for (int i = 1; i <= n; i++) {
		dis[i] = inf;
	}
	dis[st] = 0;
	cnt[st] = 1;
	s.insert({0, st});
	while (s.size()) {
		int v = (*s.begin()).second;
		s.erase(s.begin());
	//	cout << "74 " << v << endl;
		for (auto p : adj[v]) {
			long long u = p.first, w = p.second;
		//	cout << "73 " << v << " " << u << endl;
			if (dis[v] + w < dis[u]) {
				
				s.erase({dis[u], u});
				dis[u] = dis[v] + w;
				cnt[u] = 0;
				s.insert({dis[u], u});
			}
			if (dis[v] + w == dis[u]) {
				cnt[u] += cnt[v];
				cnt[u] %= mod;
			}
		}
	}
}

int32_t main() {
	int st, ed;
	cin >> n >> m >> st >> ed;
	for (int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		w *= 2;
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}
	dij(st, dis1, dp1);
	dij(ed, dis2, dp2);
//	for (int i = 1; i <= n; i++) {
//		cout << "72 " << dis1[i] << " " << dis2[i] << endl;
//	}
	long long ans = 1ll * dp1[ed] * dp1[ed];
	ans %= mod;
//	cout << "71 " << ans << endl;
	long long d = dis1[ed];
	for (int i = 1; i <= n; i++) {
		if (dis1[i] == d / 2) {
			long long x = 1ll * dp1[i] * dp2[i];
			x %= mod;
			x *= x;
			x %= mod;
			ans -= x - mod;
			ans %= mod;
		}
		for (auto p : adj[i]) {
			long long u = p.first, w = p.second;
			if (dis1[i] < d / 2 && d / 2 < dis1[u] && 0ll + dis1[i] + w + dis2[u] == d) {
				long long x = 1ll * dp1[i] * dp2[u];
				x %= mod;
				x *= x;
				x %= mod;
				ans -= x - mod;
				ans %= mod;
			}
		}
	}
	cout << ans;
	return 0;
}


Measured memory_bytes: 25840
import bisect
import math
import sys
from collections import Counter, defaultdict, deque
from copy import copy, deepcopy
from heapq import heapify, heappop, heappush
from itertools import combinations, permutations
from queue import Queue

read = sys.stdin.read
readline = sys.stdin.readline 
readlines = sys.stdin.readlines 

def SI():
    return int(readline())
def MI():
    return map(int, readline().split())
def MLI():
    return map(int, open(0).read().split())

inf = float("inf")


def main():
    n = int(input())
    S = [i for i in MI()]
    
    q = int(input())
    T = [i for i in MI()]
    
    ret = 0
    for t in T:
        index = bisect.bisect_left(S, t)
        if index < n and S[index] == t:
            ret += 1
            
    print(ret)

if __name__ == "__main__":
    main()


Measured memory_bytes: 17640
using System;
using System.Linq;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        var sol = new Solve();
        sol.Exec();
    }
}

class Solve
{
    public void Exec()
    {
        var l = Console.ReadLine().Split().Select(int.Parse).ToArray();
        int n = l[0], a = l[1], b = l[2];

        var ans = Util.Power(2, n) - 1;
        ans -= Util.Comb(n, a);
        ans -= Util.Comb(n, b);

        Console.WriteLine(ans);
    }
}

public class Util
{
    public static ModInt Comb(int n, int r)
    {
        ModInt res = 1;
        for (int i = 1; i <= r; i++)
        {
            res *= n;
            res /= i;
            n--;
        }
        return res;
    }

    public static ModInt Power(ModInt n, long m)
    {
        ModInt pow = n;
        ModInt res = 1;
        while (m > 0)
        {
            if ((m & 1) == 1) res *= pow;
            pow *= pow;
            m >>= 1;
        }
        return res;
    }
}


public struct ModInt
{
    public const int Mod = 1000000007;
    const long POSITIVIZER = ((long)Mod) << 31;
    long Data;
    public ModInt(long data) { if ((Data = data % Mod) < 0) Data += Mod; }
    public static implicit operator long(ModInt modInt) => modInt.Data;
    public static implicit operator ModInt(long val) => new ModInt(val);
    public static ModInt operator -(ModInt a, int b) => new ModInt() { Data = (a.Data - b + POSITIVIZER) % Mod };
    public static ModInt operator -(ModInt a, ModInt b) { long res = a.Data - b.Data; return new ModInt() { Data = res < 0 ? res + Mod : res }; }
    public static ModInt operator *(ModInt a, int b) => new ModInt(a.Data * b);
    public static ModInt operator *(ModInt a, ModInt b) => new ModInt() { Data = a.Data * b.Data % Mod };
    public static ModInt operator /(ModInt a, ModInt b) => new ModInt() { Data = a.Data * GetInverse(b) % Mod };
    public override int GetHashCode() => (int)Data;
    static long GetInverse(long a)
    {
        long div, p = Mod, x1 = 1, y1 = 0, x2 = 0, y2 = 1;
        while (true)
        {
            if (p == 1) return x2 + Mod; div = a / p; x1 -= x2 * div; y1 -= y2 * div; a %= p;
            if (a == 1) return x1 + Mod; div = p / a; x2 -= x1 * div; y2 -= y1 * div; p %= a;
        }
    }
}


Measured memory_bytes: 13396
#include<stdio.h>
const int mod=1e9+7;
typedef long long ll;
ll n,k;
ll ans;

int main()
{
	scanf("%lld%lld",&n,&k);
	for(ll i=k;i<=n+1;i++)
	{
		ll l=(i-1)*i>>1,r=(n+n-i+1)*i>>1;
		ans+=r-l+1;
		ans%=mod;
	}
	printf("%lld\n",ans);
	return 0;
}


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

int main() {
    long long n;
    cin >> n;
    
    stack<long long> sta;
    for (int x : {3, 5, 7}) {
        sta.emplace(x);
    }
    
    auto check = [](long long x) {
        string s = to_string(x);
        bool ret = true;
        for (char c : {'3', '5', '7'}) {
            ret &= (s.find(c) != string::npos);
        }
        return ret;
    };
    
    int ans = 0;
    while (not sta.empty()) {
        const long long k = sta.top();
        sta.pop();
        if (n < k) continue;
        if (check(k)) ans++;
        for (int x : {3, 5, 7}) {
            sta.emplace(k * 10 + x);
        }
    }
    
    cout << ans << '\n';
    
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout<< (x) << " "

int main(){
    int a,b;cin>>a>>b;
    int ans =0;
    if(a>b){ans+=a;a--;}else{ans+=b;b--;}
    if(a>b){ans+=a;}else{ans+=b;}
    co(ans);

}


Measured memory_bytes: 256
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def input():
    return sys.stdin.readline().strip()

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def main():
    INF = 999999999999999999999999
    MOD = 10**9+7

    n = int(input())
    ans = 0

    for a in range(1, n):
        b = 1
        while a*b < n:
            ans += 1
            b += 1
    
    print(ans)

main()

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

struct UnionFind {
    vector<ll> par;  // par[i]: parent of i
    vector<ll> siz;

    UnionFind(ll N) : par(N + 1), siz(N + 1, 1ll) {  // initialize by making every node a root node
        for (int i = 0; i <= N; i++) par[i] = i;
    }

    ll root(ll x) {  // find the root of a given node
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(ll x, ll y) {
        ll rx = root(x);
        ll ry = root(y);
        if (rx == ry) return;
        if (siz[rx] < siz[ry]) swap(rx, ry);
        siz[rx] += siz[ry];
        par[ry] = rx;
        return;
    }

    bool issame(ll x, ll y) {  // return true if x and y belong to the same tree
        return root(x) == root(y);
    }

    ll size(ll x) {
        return siz[root(x)];
    }
};

int main() {
	int n, m;
    cin >> n >> m;
    UnionFind uft(n);
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        uft.unite(a, b);
    }

    ll ans = 0;
    for (int i = 0; i < n; ++i) {
        ans = max(ans, uft.size(i));
    }
    cout << ans << endl;
    
}


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

typedef long long i64;

const int MAXN = 2000 + 5;
const int MOD = 1e9 + 7;

int N, K;
i64 fact[MAXN * MAXN], inverse[MAXN * MAXN];
i64 DP[MAXN][MAXN];

i64 modularExp(i64 base, i64 exp)
{
	i64 ret = 1;
	while (exp)
	{
		if (exp & 1)
			ret = ret * base % MOD;
		base = base * base % MOD;
		exp = exp >> 1;
	}
	return ret;
}

void prepare()
{
	fact[0] = 1;
	for (int i = 1; i < MAXN * MAXN; i++)
		fact[i] = fact[i - 1] * i % MOD;

	inverse[MAXN * MAXN - 1] = modularExp(fact[MAXN * MAXN - 1], MOD - 2) % MOD;
	for (int i = MAXN * MAXN - 2; i >= 0; i--)
		inverse[i] = inverse[i + 1] * (i + 1) % MOD;

	assert(inverse[1] == 1);
}

i64 getC(int n, int m)
{
	return fact[n] * inverse[m] % MOD * inverse[n - m] % MOD;
}

int main()
{
	prepare();
	cin >> N >> K;

	if(K == 1)
		cout << 1 << endl, exit(0);

	DP[0][0] = 1;
	for (int i = 0; i <= N; i++)
		for (int j = i; j <= N; j++)
		{
			DP[i][j + 1] = (DP[i][j + 1] + DP[i][j]) % MOD;
			DP[i + 1][j] = (DP[i][j] * getC(K * (N - i) - (j - i) - 1, K - 2)
					+ DP[i + 1][j]) % MOD;
		}
	cout << DP[N][N] * fact[N] % MOD << endl ;
	return 0;
}


Measured memory_bytes: 94464
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int a, b;
  cin >> a >> b;
  cout << ((a * b) % 2 == 0 ? "Even" : "Odd") << endl;
  return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main
{
    public static void main(String [] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); int k = sc.nextInt();
        int [] a = new int [n]; for (int i = 0; i < n; i++) a[i] = sc.nextInt();
        int [] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= Math.min(i, k); j++) {
                dp[i] = Math.min(dp[i], dp[i - j] + Math.abs(a[i] - a[i - j]));
            }
        }
        System.out.println(dp[n-1]);
    }


}

Measured memory_bytes: 59652
#include<iostream>
int64_t N,P,p,i,r,v,m[1<<20];std::string S;main(){std::cin>>N>>P>>S;if(10%P)for(*m=p=1;N--;r+=m[v=(v+(S[N]-48)*(p=p*10%P))%P]++);else for(;i<N;r+=(S[i++]-8)%P?0:i);std::cout<<r;}

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

int main() {
  int N;
  cin >> N;
  vector<vector<int>> V(3,vector<int>(N));
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < N; j++)
      cin >> V.at(i).at(j);
  }
  
  int count = 0;
  for (int k = 0; k < N; k++) {
    count += V.at(1).at(V.at(0).at(k) - 1);
    
    if (k < N - 1) {
      if (V.at(0).at(k) == V.at(0).at(k + 1) - 1)
        count += V.at(2).at(V.at(0).at(k) -1);
    }
  }
  
  cout << count << endl;
}


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

#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;
const int mod = (int)1e9 + 7;
void dbg(){ cerr << "\n"; }  template <typename T,typename ...T2> 
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }



int main(){
	VI ds(6);
	rep(i,6) cin >>ds[i];
	map<int, int> mp;
	rep(i,6) mp[ds[i]] = i;
	int fx[6][6] ={
		{2,4,5,3}, {4,1,3,6}, {1,5,6,2},
		{1,2,6,5}, {1,4,6,3}, {2,3,5,4}, 
	};
	int n;
	cin >>n;
	rep(g,n){
		int aa, bb;
		cin >>aa >>bb;
		int a=mp[aa]+1, b=mp[bb]+1;
		int ps= -1;
		rep(i, 4){
			if(fx[a-1][i] == b){ ps=i; break;}
		}
		
		cout << ds[fx[a-1][(ps-1+4)%4]-1] <<"\n";
	}
	
	return 0;
}




Measured memory_bytes: 3104
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int (i)=(0);(i)<(long long)(n);++(i))
using ll = long long;
using P = pair<int, int>;
using namespace std;

template<class T> void vin(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
}

struct Edge {
    int s, t, w;
};

int main() {
    int L;
    cin >> L;
    vector<Edge> g;
    int r = log2(L);
    int n = r + 1;
    rep(i, r) {
        Edge e1, e2;
        e1.s = i+1;
        e1.t = i+2;
        e1.w = 0;
        e2.s = i+1;
        e2.t = i+2;
        e2.w = pow(2, i);
        g.push_back(e1);
        g.push_back(e2);
    }
    int t = n-1;
    for (; t>=1; --t) {
        int a = pow(2, t-1);
        if (L-a>=pow(2, r)) {
            Edge e;
            e.s = t;
            e.t = n;
            e.w = L-a;
            L -= a;
            g.push_back(e);
        }
    }
    cout << n << ' ' << g.size() << endl;
    for (auto e : g) {
        cout << e.s << ' ' << e.t << ' ' << e.w << endl;
    }
    return 0;
}


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

using namespace std;
using ll=long long;

const int MAX = 200001;

typedef struct Island
{
    bool from1; // 島1 との定期便があるか
    bool toN;   // 島N との定期便があるか
}
Island;

Island island[MAX];

int main()
{
    ll N, M;
    cin >> N >> M;
    
    for (int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;
        
        if (a == 1)
        {
            island[b].from1 = true;
        }
        if (b == N)
        {
            island[a].toN = true;
        }
    }
    
    bool isPossible = false;
    for (int i = 2; i < N; i++)
    {
        // 島1 との定期便、島N との定期便があれば2回でたどり着ける
        if (island[i].from1 == true && island[i].toN == true)
        {
            isPossible = true;
            break;
        }
    }
    
    printf("%s\n", isPossible ? "POSSIBLE" : "IMPOSSIBLE");
    
    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
int main(){
  long long Q,H,S,D,N;
  cin >> Q >> H >> S >> D >> N;
  vector<long long> value(4);
  value.at(0)=8*Q;
  value.at(1)=4*H;
  value.at(2)=2*S;
  value.at(3)=D;
  vector<long long> value2(3);
  value2.at(0)=4*Q;
  value2.at(1)=2*H;
  value2.at(2)=S;
  sort(value.begin(),value.end());
  sort(value2.begin(),value2.end());
  if(N%2==0){
    cout << value.at(0)*N/2 << endl;
  }else{
    cout << value.at(0)*(N/2)+value2.at(0) << endl;
  }
}

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

using namespace std;

#define REP(i,n) for(int i=0; i<int(n); i++)
#define FOR(i,m,n) for(int i=int(m); i<int(n); i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define VI vector<int>
#define VLL vector<long long>
#define VVI vector<vector<int>>
#define VVLL vector<vector<long long>>
#define VC vector<char>
#define VS vector<string>
#define VVC vector<vector<char>>
#define fore(i,a) for(auto &i:a)
typedef long long ll;
typedef pair <int, int> P;
template<class T> bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
const int  INF = 2147483647;
const ll INFL = 9223372036854775807;
const ll mod = 1000000007;

template<class Abel> struct UnionFind {
	vector<int> par;
	vector<int> rank;
	vector<Abel> diff_weight;

	UnionFind(int n = 1, Abel SUM_UNITY = 0) {
		init(n, SUM_UNITY);
	}

	void init(int n = 1, Abel SUM_UNITY = 0) {
		par.resize(n); rank.resize(n); diff_weight.resize(n);
		for (int i = 0; i < n; ++i) par[i] = i, rank[i] = 0, diff_weight[i] = SUM_UNITY;
	}

	int root(int x) {
		if (par[x] == x) {
			return x;
		}
		else {
			int r = root(par[x]);
			diff_weight[x] += diff_weight[par[x]];
			return par[x] = r;
		}
	}

	Abel weight(int x) {
		root(x);
		return diff_weight[x];
	}

	bool issame(int x, int y) {
		return root(x) == root(y);
	}

	bool merge(int x, int y, Abel w) {
		w += weight(x); w -= weight(y);
		x = root(x); y = root(y);
		if (x == y) return false;
		if (rank[x] < rank[y]) swap(x, y), w = -w;
		if (rank[x] == rank[y]) ++rank[x];
		par[y] = x;
		diff_weight[y] = w;
		return true;
	}

	Abel diff(int x, int y) {
		return weight(y) - weight(x);
	}
};

int main() {
	int n, m;
	cin >> n >> m;
	UnionFind<int> uf(n);
	for (int i = 0; i < m; ++i) {
		int l, r, d;
		cin >> l >> r >> d;
		--l, --r;
		if (uf.issame(l, r)) {
			int diff = uf.diff(l, r);
			if (diff != d) {
				cout << "No" << endl;
				return 0;
			}
		}
		else {
			uf.merge(l, r, d);
		}
	}
	cout << "Yes" << endl;
}


Measured memory_bytes: 1408
#pragma GCC optimize("O3")
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
template<class T> using V=vector<T>; 
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
const ll mod=1000000007;
//const ll mod=998244353;
ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;}
ll lcm(ll c,ll d){return c/gcd(c,d)*d;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
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 (a>b) { a=b; return 1; } return 0; }
int main(){
ll n,a,b;
cin>>n>>a>>b;
if(a%2==b%2){
    cout<<(b-a)/2<<endl;
}
else{
    ll l=inf,r=inf;
   if(b-a>=3){
        l=a;
        l+=(b-a)/2;
        r=n-b+1;
        r+=(n-a-(n-b))/2;
   }
    cout<<min({l,r,max(a-1,b-1),max(n-a,n-b)})<<endl;
}
}

Measured memory_bytes: 256
#pragma target("avx")
#include<bits/stdc++.h>
using ll = int_fast64_t;
using P = std::pair<ll,ll>;
using V = std::vector<ll>;
template<typename T> using pq = std::priority_queue<T>;
template<typename T> using rpq = std::priority_queue<T, std::vector<T>, std::greater<T>>;

#define rep(i,b,e) for(ll i=b; i<e; i++)
#define be(vec) vec.begin(),vec.end()
#define print(vec) printf("[ ");for(auto &i:vec)printf("%ld ",i);puts("]");
#define scan(vec) for(auto &i:vec)scanf("%ld",&i)
#define fi first
#define se second

const int MOD = 1e9+7;
const ll INF = 1e18;
int dx[] = {0, 1, 0, -1, 1, 1, -1, -1}, dy[] = {1, 0, -1, 0, 1, -1, -1, 1};

int main(){
	ll a, b;
	scanf("%ld %ld", &a, &b);
	if(a==0 or b==0 or a<0 and 0<b or b<0 and 0<a) puts("Zero");
	else if(a>0 and b>0) puts("Positive");
	else{
		if((a-b)%2) puts("Positive");
		else puts("Negative");
	}
	return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>

#define INF (1e+9)
#define LLINF (1e+18)
#define LL long long

#define MAX_V 5000
#define MAX_E 10000
#define MAX_ABLE 5000

using namespace std;


typedef struct node{
public:
	int fare;
	int able;
	node(){

	}
	node(int _fare,int _able){
		fare = _fare;
		able = _able;
	}
}node;

typedef struct edge{
public:
	int to;
	int cost;
	int rest;
	edge(){

	}
	edge(int _to,int _cost,int _rest){
		to = _to;
		cost = _cost;
		rest = _rest;
	}
	bool operator<(const edge &a)const{
		if(cost == a.cost) return rest < a.rest;
		return cost > a.cost;	//for asc
	}
}edge;

node city[MAX_V + 1];
vector<int > G[MAX_V + 1];

int cost[MAX_V + 1][MAX_ABLE + 1];

priority_queue<edge> pque;

int V;
int E;


void solve(){
	for(int i = 0;i < MAX_V + 1;i++){
		for(int j = 0;j < MAX_ABLE + 1;j++){
			cost[i][j] = INF;
		}
	}

	/*pque.push(edge(1,0,0));

	while(!pque.empty()){
		edge e = pque.top();pque.pop();
		if(cost[e.to][e.rest] != INF) continue;
		cost[e.to][e.rest] = e.cost;
		
		for(int i = 0;i < G[e.to].size();i++){
			int _to = G[e.to][i];
			int _cost = e.cost;
			int _rest = e.rest;
			if(_rest != 0) pque.push(edge(_to,_cost,_rest - 1));
			pque.push(edge(_to,_cost + fare[e.to],able[e.to]));
		}
	}*/

	pque.push(edge(1,0,0));

	while(!pque.empty()){
		edge e = pque.top();pque.pop();
		if(cost[e.to][e.rest] != INF) continue;
		cost[e.to][e.rest] = e.cost;

		for(int i = 0;i < G[e.to].size();i++){
			int _to = G[e.to][i];
			if(e.rest != 0) pque.push(edge(_to,e.cost,e.rest - 1));
			pque.push(edge(_to,e.cost + city[e.to].fare,city[e.to].able - 1));
		}
	}

	/*for(int i = 1;i < V + 1;i++){
		printf("###");
		for(int j = 0;j < 10;j++){
			printf(" %d",cost[i][j]);
		}
		puts("");
	}*/


	return ;
}


int main (void){

	scanf("%d%d",&V,&E);
	int _fare;
	int _able;
	for(int i = 1;i < V + 1;i++){
		scanf("%d%d",&_fare,&_able);
		city[i] = node(_fare,_able);
	}
	int _u,_v;
	for(int i = 0;i < E;i++){
		scanf("%d%d",&_u,&_v);
		G[_u].push_back(_v);
		G[_v].push_back(_u);
	}

	/*for(int i = 1;i < V + 1;i++){
		printf("###");
		for(int j = 0;j < G[i].size();j++){
			printf(" %d",G[i][j]);
		}
		puts("");
	}*/

	solve();

	int ans = INF;
	for(int i = 0;i < MAX_ABLE + 1;i++){
		ans = min(ans,cost[V][i]);
	}

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

	return 0;
}

Measured memory_bytes: 102216
#include <bits/stdc++.h>
using namespace std;
int a[100005],b[100005],n,m,l,r,p,q; char S[100005],T[100005];
int main(){
	scanf("%s",S+1); n=strlen(S+1);
	for (int i=1;i<=n;++i) a[i]=(a[i-1]+(S[i]=='A'?1:-1)+3)%3;
	scanf("%s",T+1); m=strlen(T+1);
	for (int i=1;i<=m;++i) b[i]=(b[i-1]+(T[i]=='A'?1:-1)+3)%3;
	scanf("%d",&n);
	while (n--){
		scanf("%d%d%d%d",&l,&r,&p,&q);
		(a[r]-a[l-1]+3)%3==(b[q]-b[p-1]+3)%3?puts("YES"):puts("NO");
	}
	return 0;
}

Measured memory_bytes: 1536
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>

#define int long long
#define MOD 1000000007

#define rep(i, n) for (int i = 0; i < (n); i++)
#define REP(i, a, n) for (int i = (a); i <= (n); i++)
#define all(a) (a).begin(), (a).end()
#define mp(a, b) make_pair((a), (b))

using namespace std;

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

signed main() {
	int N;
	cin >> N;

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

	int ret = 0;
	for (int num : a) ret += num - 1;

	cout << ret << endl;
}


Measured memory_bytes: 384
def collatz(n: int) -> int:
    if n % 2 == 0:
        return n // 2
    else:
        return 3 * n + 1


def collatz_problem(s: int) -> int:
    if s == 1 or s == 2 or s == 4:
        return 1 + 3

    i = 1
    while True:
        i += 1
        s = collatz(s)
        if s == 4:
            return i + 3

    return - 1


if __name__ == "__main__":
    s = int(input())
    ans = collatz_problem(s)
    print(ans)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int a,b;
    char c;
    cin >> a >> c >> b;
    if (c == '-') {
        cout << a - b << endl;
    }
    else {
        cout << a + b << endl;
    }

}

Measured memory_bytes: 3628
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static int AMAX = 200000;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = new int[n];
		for(int i=0;i<n;i++) {
			a[i] = sc.nextInt();
		}
		double[][] dp = new double[n+1][AMAX+1];
		for(int i=0;i<=n;i++) {
			Arrays.fill(dp[i], Double.POSITIVE_INFINITY);
		}
		dp[0][1] = 0;
		for(int i=0;i<n;i++) {
			for(int j=1;j<=AMAX;j++) {
				if (dp[i][j] >= Double.POSITIVE_INFINITY) {
					continue;
				}
				for(int k=j;k<=AMAX;k+=j) {
					dp[i+1][k] = Math.min(dp[i+1][k], Math.max(dp[i][j],(double) Math.abs(a[i] - k) / a[i]));
				}
			}
		}
//		for(int i=0;i<=n;i++) {
//			for(int j=0;j<=100;j++) {
//				System.out.print(String.format("%10f,",dp[i][j]));
//			}
//			System.out.println();
//		}
		double ans = Double.POSITIVE_INFINITY;
		for(int i=1;i<=AMAX;i++) {
			ans = Math.min(ans, dp[n][i]);
		}
		System.out.println(String.format("%.9f", ans));
	}

}

Measured memory_bytes: 86384
import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def s(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")

S = X()
p = set(S)
if len(S) == 1:
    print("YES")
    sys.exit()

if len(p) == 1:
    print("NO")
    sys.exit()

a = S.count("a")
b = S.count("b")
c = S.count("c")
cnt = len(S)//3

if len(S) % 3 == 0:
    if a <= cnt and b <=cnt and c<= cnt:
        print("YES")
    else:
        print("NO")
else:
    if a <= cnt+1 and b <=cnt+1 and c<= cnt+1:
        print("YES")
    else:
        print("NO")


Measured memory_bytes: 10996
#include <iostream>
#include <cstdio>

int main(int argc, const char * argv[])
{
    int n, a, b, c;
    scanf("%d", &n);
    
    for (int i = 0; i < n; i++) {
        scanf("%d %d %d", &a, &b, &c);
        if (a*a + b*b == c*c) {
            printf("YES\n");
        }
        else if (b*b + c*c == a*a) {
            printf("YES\n");
        }
        else if (c*c + a*a == b*b) {
            printf("YES\n");
        }
        else
            printf("NO\n");
    }
    return 0;
}

Measured memory_bytes: 1172
use proconio::input;
 
fn main() {
  input! {
    n: usize,
    mut k: usize,
    mut vals: [isize;n]
  }
  
  let mut min = isize::max_value();
  let mut index = n-1;
  loop {
    let i = index - k + 1;
    min = std::cmp::min(
      min,
      vals[index].abs() + (vals[index] - vals[i]).abs()
    );
    
    if i == 0 { break }
    index -= 1;
  }
  
  let mut index = 0;
  loop {
    let i = index + k-1;
    min = std::cmp::min(
      min,
      vals[index].abs() + (vals[index] - vals[i]).abs()
    );
    
    if n-1 <= i { break }
    index += 1;
  }
  println!("{}", min);
}

Measured memory_bytes: 3664
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
typedef vector<vector<P>> vvP;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;

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

    ll u = 2;
    ll ans = a0-1;
    rep(i, n-1) {
        ll a;
        cin >> a;
        if(a == u) {
            u++;
        }
        else if(a > u) {
            ans += (a-1)/u;
        }
    }

    out(ans);
    re0;
}

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

typedef long long ll;
using namespace std;

bool graph[8][8];

int dfs(int v, int N, bool visited[8]) {
  bool all_visited = true;
  for (int i = 0; i < N; i++) {
    if (visited[i] == false) {
      all_visited = false;
    }
  }

  if (all_visited) {
    return 1;
  }

  int ret = 0;

  for (int i = 0; i < N; i++) {
    if (graph[v][i] == false)
      continue;
    if (visited[i])
      continue;
    visited[i] = true;
    ret += dfs(i, N, visited);
    visited[i] = false;
  }
  return ret;
}

int main() {
  int N, M;
  cin >> N >> M;

  for (int i = 0; i < M; i++) {
    int A, B;
    cin >> A >> B;
    graph[A - 1][B - 1] = graph[B - 1][A - 1] = true;
  }

  bool visited[8];
  for (int i = 0; i < N; i++) {
    visited[i] = false;
  }

  visited[0] = true;
  cout << dfs(0, N, visited) << endl;
  return 0;
}

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

string zero_padding(int n) {
  if (n == 0) { return "000"; }

  int n_copy = n;
  int digits = 0;
  while (n>0) {
    n = n / 10;
    digits++;
  }
  string s;
  for (int i = 0; i < (3-digits); i++) {
    s += '0';
  }
  return s+to_string(n_copy);
}

int main() {
  int n;
  string s;
  cin >> n >> s;

  int ans = 0;
  for (int i = 0; i < 1000; i++) {
    string p = zero_padding(i);
    size_t a = s.find_first_of(p.at(0));
    size_t b = s.find_first_of(p.at(1), a+1);
    size_t c = s.find_first_of(p.at(2), b+1);
    if (a != string::npos && b != string::npos && c != string::npos
        && a < b && b < c) {
      ans++;
    }
  }

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


Measured memory_bytes: 3756
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

int n;

int main(){
	cin>>n;
	int M=0,B=0;
	for(int i=0;i<n;i++){
		int x;
		cin>>x;
		B|=x%2;
		M=max(M,x);
	}
	B|=M%2;
	cout<<(B?"first":"second")<<endl;
}

Measured memory_bytes: 384
#include<string>
#include<iostream>
#include<algorithm>
#include<set>
#include<math.h>
#include<vector>
#include<sstream>
#include<queue>
#include<functional>
#include<bitset>
#include<cstdio>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include <string.h>
using ll = long long;

#define rep(i, n) for(ll i = 0; i < (int)(n); i++)
#define reps(i,x) for(ll i=1;i<=(int)(x);i++)
#define rrep(i,x) for(ll i=((int)(x)-1);i>=0;i--)
#define rreps(i,x) for(ll i=(int)(x);i>0;i--)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))
#define vll vector<ll>
#define vi vector<int>
#define mp make_pair
#define vpll vector<pair<ll,ll>>
#define vpi vector<pair<int,int>>
#define mod 1000000007 
using namespace std;
ll n, m;
ll p[200005];
int main() {
	cin >> n;
	ll ans = 0;
	ll t;
	reps(i, n) {
		cin >> t;
		ans = max(ans, p[t]=p[t-1]+1);
	}
	cout << n-ans << endl;
	return 0;
}

Measured memory_bytes: 1916
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;
using ll = long long int;
using int64 = long long int;
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const int INF = 1LL << 29;
const ll LONGINF = 1LL << 60;
const ll MOD = 1000000007LL;
 
int main() {
    int H, W, N; cin >> H >> W >> N;
    cout << min((N + W - 1) / W, (N + H - 1) / H) << endl;
    return 0;
}


Measured memory_bytes: 256
n = gets.to_i
exit if n <3
#PWGY
val = [0,0,0,0]
arares = gets.chomp.split(" ")
n.times do|i|
   val[0] =val[0]+1  if arares[i] == "P" && val[0]==0
   val[1] =val[1]+1  if arares[i] == "W" && val[1]==0
   val[2] =val[2]+1  if arares[i] == "G" && val[2]==0
   val[3] =val[3]+1  if arares[i] == "Y" && val[3]==0
end
case val.inject {|sum, n| sum + n }
when 3 then
  puts "Three"
when 4 then
  puts "Four"
else
end


Measured memory_bytes: 3836
#include"bits/stdc++.h"
#include<boost/multi_array.hpp>
#include<boost/range/irange.hpp>
#include<boost/range/algorithm.hpp>
#include<boost/range/adaptors.hpp>

namespace adaptor = boost::adaptors;

int64_t A, B, C, X, Y;

void solve()
{
	std::cin >> A >> B >> C >> X >> Y;

	int64_t ans1 = A * X + B * Y;
	int64_t ans2;
	if (X < Y)
	{
		ans2 = C * X * 2 + B * (Y - X);
	}
	else
	{
		ans2 = C * Y * 2 + A * (X - Y);
	}
	int64_t ans3 = C * std::max(X, Y) * 2;

	int64_t ans = std::min(ans1, std::min(ans2, ans3));
	std::cout << ans << std::endl;
}

int main()
{
	std::cin.tie(nullptr);
	std::ios_base::sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(15);
	solve();
}


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

//repetition
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

//container util
#define all(x) (x).begin(),(x).end()

//typedef
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;

//const value
//const ll MOD = 1e9 + 7;
//const int dx[] = {0,1,0,-1};//{0,0,1,1,1,-1,-1,-1};
//const int dy[] = {1,0,-1,0};//{1,-1,0,1,-1,0,1,-1};

//conversion
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
inline ll toLL(string s) {ll v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}


int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int h,w,k;
  cin >> h >> w >> k;
  string board[h];
  rep(i,h) cin >> board[i];
  int ans[h][w];
  rep(i,h) rep(j,w) ans[i][j] = -1;

  VI cnt(h,0);
  
  rep(i,h) rep(j,w){
    if(board[i][j] == '#') cnt[i]++;
  }

  int c = 1;
  rep(i,h){
    if(cnt[i] == 0) continue;
    rep(j,w){
      if(board[i][j] == '.') ans[i][j] = c;
      else{
        ans[i][j] = c;
        cnt[i]--;
        if(cnt[i] > 0) c++;
      }
    }
    c++;
  }

  rep(i,h-1) {
    rep(j,w){
      if(ans[i][j] > 0 && ans[i+1][j] < 0) ans[i+1][j] = ans[i][j];
    }
  }

  for(ll i = h-1; i >= 1; i--){
    rep(j,w){
      if(ans[i][j] > 0 && ans[i-1][j] < 0) ans[i-1][j] = ans[i][j];
    }
  }

  rep(i,h){
    rep(j,w){
      cout << ans[i][j] << " ";
    }
    cout << endl;
  }
  return 0;
}


Measured memory_bytes: 1280
#include <iostream>
#include <functional>

using namespace std;

class Card {
	int power;
public:
	Card(int x) {
		power = x == 1 ? 99999 : x;
	}

	bool  operator==(Card other)const {
		return ((*this > other) || (*this < other)) == false;
	}

	bool  operator<(Card other)const {
		return power < other.power;
	}

	bool  operator>(Card other)const {
		return other < *this;
	}
};

int main() {
	int a, b;
	cin >> a >> b;
	auto ca = Card(a);
	auto cb = Card(b);
	cout << (ca == cb ? "Draw" : ca > cb ? "Alice" : "Bob") << endl;
}


Measured memory_bytes: 256
n=int(input())
s=input()
list=["" for _ in range(1000)]
ans=0
for i in range(1000):
  t=str(i)
  u="0"*(3-len(t))+t
  j=0
  exi=0
  p=u[0]
  for x in s:
    if x==p:
      j+=1
      if j==3:
        ans+=1
        break
      p=u[j]
    

  









print(ans)


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define r(i,n) for(int i=0;i<n;i++)
int v1[203][203],v2[203][203],a1,a2,a3,n,m;
int dp[2][203][203],t,x,pre;
char c;
int main(){
  while(cin>>n>>m,n){
    int ans=1e8;
    r(i,2)r(j,203)r(k,203)dp[i][j][k]=1e8;
    r(i,203)r(j,203)v1[i][j]=v2[j][i]=(i==j?0:1e8);
    r(i,m){
      cin>>a1>>a2>>a3>>c;
      a1--,a2--;
      if(c=='L')v1[a1][a2]=v1[a2][a1]=a3;
      else v2[a1][a2]=v2[a2][a1]=a3;
    }
    r(k,n)r(i,n)r(j,n){
      v1[i][j]=min(v1[i][j],v1[i][k]+v1[k][j]);
      v2[i][j]=min(v2[i][j],v2[i][k]+v2[k][j]);
    }
    cin>>t>>pre;pre--;
    dp[0][pre][pre]=0;
    for(int k=0;k<t-1;k++){
      cin>>x;x--;
      for(int i=0;i<n;i++){
        dp[(k+1)%2][x][i]=min(dp[(k+1)%2][x][i],dp[k%2][pre][i]+v1[pre][x]);
        for(int j=0;j<n;j++){
          dp[(k+1)%2][x][j]=min(dp[(k+1)%2][x][j],dp[k%2][pre][i]+v1[pre][i]+v2[i][j]+v1[j][x]);
        }
      }
      r(i,203)r(j,203)dp[k%2][i][j]=1e8;
      pre=x;
    }
    r(i,203)ans=min(ans,dp[(t-1)%2][pre][i]);
    cout<<ans<<endl;
  }
}

Measured memory_bytes: 3628
//In the Name of God
//Ya Ali

#include <bits/stdc++.h>

#define err(A) cout << #A << " = " << (A) << endl

using namespace std;

const int mod = 1e9 + 7;;
const int maxn = 3030;

int h, w;

string s[maxn];

int dp[maxn][maxn];

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

  cin >> h >> w;

  for (int i = 0; i < h; i ++)
    cin >> s[i];

  dp[h - 1][w - 1] = 1;
  
  for (int i = h; i --; )
    for (int j = w; j --; )
      if (s[i][j] == '.')
	dp[i][j] += (dp[i + 1][j] + dp[i][j + 1]) % mod;

  cout << (dp[0][0] % mod) << endl; 
  
  return 0;
}


Measured memory_bytes: 12928
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main(){
	long long int x;
	long long int per,sla;
	scanf("%lld",&x);
	sla=x/11;
	per=x%11;
	sla*=2;
	if(per==0) sla+=0;
	else if(per<=6) sla++;
	else sla+=2;
	printf("%lld\n",sla);
	
	return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <stack>
#include <utility>
#include <string>
#include <numeric>
#include <vector>
#include <algorithm>

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

    std::vector< int > ans;
    std::stack< std::pair< int, int > > st;
    for (int i = 0; i < s.size(); ++i) {
        if (s[i] == '_') continue;

        if (s[i] == '/') {
            if (st.empty()) {
                continue;
            }

            std::vector< std::pair< int, int > > vs;
            while (!st.empty() && st.top().second != 0) {
                vs.emplace_back(st.top());
                st.pop();
            }

            if (st.empty()) {
                std::reverse(vs.begin(), vs.end());
                for (auto &v: vs) ans.emplace_back(v.second);
            } else {
                int sum = i - st.top().first;;
                for (auto &v: vs) sum += v.second;
                st.pop();
                st.emplace(i, sum);
            }
        } else {
            st.emplace(i, 0);
        }
    }

    std::vector< int > vs;
    while (!st.empty()) {
        if (st.top().second != 0) {
            vs.emplace_back(st.top().second);
        }

        st.pop();
    }

    std::reverse(vs.begin(), vs.end());
    for (auto &v: vs) ans.emplace_back(v);

    std::cout << std::accumulate(ans.begin(), ans.end(), 0) << std::endl;

    std::cout << ans.size();
    for (auto a: ans) std::cout << " " << a;
    std::cout << std::endl;
}



Measured memory_bytes: 3320
N=int(input())
S=input()
L1,L2,L3,L4='SS','SW','WS','WW'

def make_seq(L):
    for i in range(1,N-1):
        if S[i]+L[i-1]+L[i] in ['oSS','oWW','xSW','xWS']:
            L+='S'
        else:
            L+='W'
    return L

T=['oSSS','oWSW','oSWW','oWWS','xWSS','xSSW','xSWS','xWWW']
def check(L):
    if S[0]+L[-1]+L[0]+L[1] in T and S[-1]+L[-2]+L[-1]+L[0] in T:
        return L
    else:
        return -1

L1=make_seq(L1)
L2=make_seq(L2)
L3=make_seq(L3)
L4=make_seq(L4)
C=[check(L1),check(L2),check(L3),check(L4)]

import sys
for i in C:
    if i!=-1:
        print(i)
        sys.exit()
print(-1)

Measured memory_bytes: 3700
#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define f(i,x,n) for(int i=x;i<n;i++) 
#define all(c) c.begin(),c.end()
const int MOD = 1e9 + 7, N = 5e5 + 10;
const int LINF = LLONG_MAX;

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s,ss;
    
    cin >> s >> ss;
    f(i,0,s.size()){
        if(s[i] != ss[i]){
            cout << "No\n";
            return 0;
        }
    }
    cout << "Yes\n";
    return 0;
}

Measured memory_bytes: 3648
x, n = map(int,input().split())
if(n != 0):
    a = list(map(int, input().split()))
    if not x in a:
        print(x)
    else:    
        l = x
        r = x
        while(True):
            r += 1
            l -= 1
            if not l in a:
                print(l)
                break
            elif not r in a:
                print(r)
                break
else:
    print(x)


    

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

using namespace std;

typedef long long ll;

int main()
{
    int N, R, K;
    cin>>N>>R;
    K=R;
    if(N>=10)
    {
        cout<<K;
    }
    else if(N<10)
    {
        K=R+100*(10-N);
        cout<<K;
    }
    return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;

namespace AtCoder
{
	public class Program
	{
		//static int[] parent;
		static void Main(string[] args)
		{
			int[] input = Console.ReadLine().Split().Select(p => int.Parse(p)).ToArray();
			int N = input[0];
			//int K = input[1];

			// 頂点から伸びる頂点とその距離のリスト
			List<List<List<int>>> tree = new List<List<List<int>>>();
			// 初期化
			for(int i=0; i<N; i++)
			{
				List<List<int>> list = new List<List<int>>();
				tree.Add(list);
			}

//Console.WriteLine("debug2 " + tree.Count);
			for(int i=0; i<N-1; i++)
			{
			//	Console.WriteLine("debug3 " + i);
				input = Console.ReadLine().Split().Select(p => int.Parse(p)).ToArray();
				// input[0]->input[1] の距離はinput[2]
				List<int> d = new List<int>();
				d.Add(input[1]);
				d.Add(input[2]);
				tree[input[0]-1].Add(d);

				// 逆向きも
				List<int> d2 = new List<int>();
				d2.Add(input[0]);
				d2.Add(input[2]);
				tree[input[1]-1].Add(d2);
			}
//Console.WriteLine("debug1");
			int[] color = new int[N];
			//HashSet<int> hs = new HashSet<int>();
			// color[0]=0
			//hs.Add(0);
			for(int i=1; i<N; i++)
			{
				color[i] = -1;
				//hs.Add(i);
			}

			// 塗り分けする
			coloring(0, tree, color);
			/*while(hs.Count > 0)
			{
				HashSet<int> dl = new HashSet<int>();
				foreach(var i in hs)
				{
					int c = color[i]; // iは何色
					if(c<0)// || comp[i] == 1)
					{
						continue; // 色未定orすでに行き先塗ってたら飛ばす
					}
					// 行き先を全て塗るとhsから外す
					dl.UnionWith(coloring(i, tree, color));
				}

				foreach(var a in dl)
				{
					hs.Remove(a);
				}
			}
			*/

			// 色分け終わり
			for(int i=0; i<N; i++)
				Console.WriteLine(color[i] + "") ;
		}

		static void coloring(int i, List<List<List<int>>> tree, int[] color)
		{
			// 行き先を深さ優先探索する
			//HashSet<int> ret = new HashSet<int>();
			//ret.Add(i);
			List<List<int>> leef = tree[i];
			for(int j=0; j<leef.Count; j++)
			{
				int node = leef[j][0]-1; // 行き先番号
				if(color[node]>=0)
					continue; // すでに塗られていたらOK

				if(leef[j][1]%2 == 0)
					color[node] = color[i];
				else
					color[node] = (color[i]+1)%2;

			 coloring(node, tree, color);
				//ret.UnionWith(coloring(node, tree, color));
			}

			//return ret;
		}
	}
}


Measured memory_bytes: 47552
#include"bits/stdc++.h"

using namespace std; 

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef vector<PII> VPII;
typedef long long LL;
typedef priority_queue<int> PQ_DESC;
typedef priority_queue<int, vector<int>, greater<int>> PQ_ASC;
typedef priority_queue<PII> PQ_DESC_PII;
typedef priority_queue<PII, vector<PII>, greater<PII>> PQ_ASC_PII;

#define ALL(c) (c).begin(),(c).end()
#define PB push_back
#define MP make_pair
#define SORT_ASC(c) sort(ALL(c))
#define SORT_DESC(c) sort(ALL(c), greater<typeof(*((c).begin()))>())
#define SIZE(a) int((a).size())

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ROF(i,a,b) for(int i=(b-1);i>=(a);--i)
#define REP(i,n) FOR(i,0,n)
#define REP(i,n) FOR(i,0,n)
#define PER(i,n) ROF(i,0,n)

const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int LARGE_INT = 1e9+100;
const int INF = 2e9+100;

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

void Main()
{
	int n; cin>>n;
	string s; cin >> s;

	int result = 1;
	FOR(i,1,n){
		if(s[i-1] != s[i]){
			result++;
		}
	}

	cout << result << endl;

	return;
}

int main()
{
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
    return 0;
}

Measured memory_bytes: 512