akhauriyash/Code-Regression huggingface dataset:
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val n = sc.nextInt()
    val k = sc.nextLong()
    val a = (0 until n).map { sc.next().toInt() }
    println(problem167d(n, k, a))
}

fun problem167d(n: Int, k: Long, a: List<Int>): Int {
    val visited = hashMapOf<Int, Int>()
    visited[1] = 0
    var loopPoint = -1 to -1
    var current = 1
    for (i in 0 until n) {
        val next = a[current-1]
        if (i.toLong() >= k - 1) {
            return next
        }
        if (visited.contains(next)) {
            loopPoint = next to i + 1 - visited[next]!!
            break
        }
        visited[next] = i + 1
        current = next
    }
    val temp = (k - visited[loopPoint.first]!!) % loopPoint.second
    current = loopPoint.first
    for (i in 0 until temp) {
        current = a[current - 1]
    }
    return current
}


Measured memory_bytes: 70044
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 9223372036854775807;
const ll MOD = 1000000007;
#define pb push_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define o0(a) cout<<a<<" "
#define o1(a) cout<<a<<"\n"
#define o2(a, b) cout<<a<<" "<<b<<"\n"
#define o3(a, b, c) cout<<a<<" "<<b<<" "<<c<<"\n"
#define i1(a) cin>>a
#define i2(a, b) cin>>a>>b
#define i3(a, b, c) cin>>a>>b>>c
#define fi first
#define se second

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

ll inverse(ll a, ll z = MOD)
{
	return power(a, z-2, z);
}

ll gcd(ll a, ll b)
{
	ll temp;
	if(a < b)
	{
		temp = a;
		a = b;
		b = temp;
	}
	while(b)
	{
		temp = b;
		b = a - b;
		a = temp;
	}
	return a;
}

ll extend(ll a, ll b, ll &x, ll &y)
{
	if(b == 0)
	{
		x = 1;
		y = 0;
		return a;
	}
	ll x1, y1;
	ll g = extend(b, a%b, x1, y1);
	x = y1;
	y = x1- (a/b)*y1;
	return g;
}

ll mat_power(ll a, ll b, ll c, ll d, ll n, ll z = MOD)
{
	ll a0 = 1, b0 = 0, c0 = 0, d0 = 1;
	while(n)
	{
		if(n&1)
		{
			ll a1 = a0, b1 = b0, c1 = c0, d1 = d0;
			a0 = (a1*a + b1*c)%z;
			b0 = (a1*b + b1*d)%z;
			c0 = (c1*a + d1*c)%z;
			d0 = (c1*b + d1*d)%z;
		}
		ll a1 = a, b1 = b, c1 = c, d1 = d;
		a = (a1*a1 + b1*c1)%z;
		b = (a1*b1 + b1*d1)%z;
		c = (c1*a1 + d1*c1)%z;
		d = (c1*b1 + d1*d1)%z;
		n = n>>1;
	}
	return c0;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t = 1;
	// i1(t);
	while(t--)
	{
		int n;
		i1(n);
		int aray[n];
		for(int i=0;i<n;i++)
			i1(aray[i]);
		int ans[n];
		int sum = aray[0];
		for(int i=1;i<n;i++)
			sum = sum^aray[i];
		for(int i=0;i<n;i++)
			ans[i] = sum^aray[i];
		for(int i=0;i<n;i++)
			o0(ans[i]);
		cout<<"\n";
	}
	return 0;
}

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

#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());


void c_p_c()
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif
}

int32_t main()
{
  //c_p_c();
  int n,k;
  cin >> n >> k;
  vector <int> a(n);
  for(int i=0;i<n;i++)
  {
    cin >> a[i];
  }
  vector <pair<int,int>> v(n);
  for(int i=0;i<n;i++)
  {
    v[i].first = a[i];
    v[i].second = INT_MIN;
  }
  for(int i=0;i<k;i++)
  {
    int x,y;
    cin >> x >> y;
    x--,y--;
    v[x].second = max(v[x].second,a[y]);
    v[y].second = max(v[y].second,a[x]);
  }
  int ans = 0;
  for(int i=0;i<v.size();i++)
  {
    if(v[i].first > v[i].second)
    {
      ans++;
    }
  }
  cout<<ans<<endl;
  return 0; 
}



Measured memory_bytes: 5624
#include <bits/stdc++.h>
using namespace std;
int b,c,e;
int main() {
    int n1,n2;
    cin>>n1;
    vector<int> a(n1);
    for(int i=0;i<n1;i++){
        cin>>a[i];
    }
    cin>>n2;
    while(n2--){
        int b,c,e;
        cin>>b>>c>>e;
        swap_ranges(a.begin()+b,a.begin()+c,a.begin()+e);
    }
    for(int i=0;i<n1;i++){
        if(i) cout<<" ";
        cout<<a[i];
    }
    cout<<endl;
}



Measured memory_bytes: 3092
package main

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

// AOJ - ALDS1
// ALDS1_1_D - Max Profit (最大の利益)
// https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/1/ALDS1_1_D

// 問題の概略
// R0,R1,....,Rn-1のn個の数が与えられた時にRj-Ri (ただしj > i)の最大値を求めよ
// 制約：
// 2 <= n <= 200,000
// 1 <= Ri <= 10^9

// 方針:
// Riのそれぞれについて、Ri-1までの最小値との差をとり、その最大値を答えとすればよいが、これはO(N^2)で間に合わない。
// 実はi-1までの最小値を追跡しておき、それとRiの差をとって利益（損失の場合もある）の最大値を追跡すればよい。これはO(N)で間に合う。

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	n := nextInt(sc)
	a := make([]int, n)
	for i := range a {
		a[i] = nextInt(sc)
	}
	minv := a[0]
	maxv := -(int(1e9) + 1)
	for i := 1; i < n; i++ {
		maxv = max(maxv, a[i]-minv)
		minv = min(minv, a[i])
	}
	fmt.Println(maxv)
}

func nextInt(sc *bufio.Scanner) int {
	sc.Scan()
	t, _ := strconv.Atoi(sc.Text())
	return t
}



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

int main(){
  string s;
  cin >> s;
  int s_num = s.length();
  char s_f = s[0], s_e = s[s_num - 1];
  cout << s_f << s_num - 2 << s_e;
  return 0;
}

Measured memory_bytes: 256
import numpy as np

N, M = map(int, input().split())
S = []

for i in range(M):
	k, *ss = map(int, input().split())
	S.append(np.asarray(ss, np.int) - 1)

P = np.fromiter(map(int, input().split()), np.int)

count = 0
for bits in range(1 << N):
	switches = (bits >> np.arange(N)) & 1
	count += all(np.sum(switches[S[i]]) % 2 == P[i] for i in range(M))

print(count)


Measured memory_bytes: 12436
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 1000000007LL;
const ll INF = 1LL << 60;
const double PI = 3.141592653589793238;
const double EPS = 1e-10;
bool use[10];
int num[10] = { 0,2,5,5,4,5,6,3,7,6 };
//dp[i]::=i本のマッチ棒を使って作れる整数の最大値
string dp[10001];
bool exist[10001];
int main() {
	int N, M;
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int A;
		cin >> A;
		use[A] = 1;
	}
	dp[0] = "";
	exist[0] = 1;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= 9; j++) {
			if (!use[j] || num[j] > i || !exist[i - num[j]]) continue;
			string t = string(1, j + '0') + dp[i - num[j]];
			if (!exist[i]) {
				dp[i] = t;
				exist[i] = 1;
			}
			else {
				if (t.size() > dp[i].size()) dp[i] = t;
				else if (t.size() == dp[i].size() && t > dp[i]) dp[i] = t;
			}
		}
	}
	cout << dp[N] << endl;
}

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

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (int i = (int)a; i < (int)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define MOD 1000000007
#define INF 1000000000
#define PI 3.14159265359
#define EPS 1e-12

int main(void) {
  int n;
  cin >> n;
  string s[110];
  REP(i, n) cin >> s[i];

  int numa = 0;
  REP(i, n) {
    if (s[i] == "A") {
      numa++;
    } else {
      if (numa > 0)
        numa--;
      else if (numa == 0) {
        cout << "NO" << endl;
        return 0;
      }
    }
  }

  if (!numa)
    cout << "YES" << endl;
  else
    cout << "NO" << endl;

  return 0;
}

Measured memory_bytes: 3160
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    long long mod = 1e9 + 7;
    vector<long long>v(n + 3), power(n + 3);
    power[0] = 1;
    for(int i = 1; i <= n; i++){
        cin >> v[i];
        power[i] = (power[i - 1] * 4) % mod;
    }
    sort(v.begin() + 1, v.begin() + n + 1);
    reverse(v.begin() + 1, v.begin() + n + 1);
    long long ans = 0;
    for(int i = 1; i <= n; i++){
        ans = (ans + 1LL * (i + 1) * v[i]) % mod;
    }
    ans = (ans * power[n - 1]) % mod;
    cout << ans;
    return 0;
}

Measured memory_bytes: 6392
#include <iostream>
using namespace std;
int main(){
  int a ,b ,ans=0;
  char s;

  cin >> ans;  

  while( cin >> s ){

    if( s == '=' ){
      break;
    }

    cin >> a;
    
    if( s == '+' ){  // 加算
      ans = ans + a;
    }  
    
    if( s == '-' ){  // 減算
      ans = ans - a;
    }  
    
    if( s == '*' ){  // 乗算
      ans = ans * a;
    }  
    
    if( s == '/' ){  // 除算
      ans = ans / a;
    }  
  }
  
  cout << ans << endl;
  return 0;
}

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

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

constexpr ll LLINF {1001002003004005006};//ll = 9*LLINF
constexpr int INTINF {1000000000};//int = 2*INTINF

#define  rep(i,n)   for(int i = 0; i < (n); ++i)
#define rrep(i,n)   for(int i = 1; i <= (n); ++i)
#define drep(i,n)   for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for(int i = s; i < t;  ++i)

template<typename T>
void maxs(T& x, T&& y) {
  x=std::max(x,y);
}
template<typename T>
void maxs(T& x, T& y) {
  x=std::max(x,y);
}

template<typename T>
void mins(T& x, T&& y) {
  x=std::min(x,y);
}
template<typename T>
void mins(T& x, T& y) {
  x=std::min(x,y);
}

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

  int a;
  cin >> a;
  int ans = a + a*a + a*a*a;
  cout << ans << '\n';
}


Measured memory_bytes: 3652
#pragma once
#include <stdio.h>
#include <sstream>
#include <string>
#include <string.h>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <deque>
#include <limits>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define bit(x,v) ((ll)x << v)

const ll INF = 1000000007;
const int MAX = 210000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
int pr[100010];
void uini(int n) {
	for (size_t i = 0; i <= n; i++)
	{
		pr[i] = i;
	}
}

int parent(int x) {
	if (x == pr[x]) return x;
	return pr[x] = parent(pr[x]);
}

bool unit(int x, int y) {
	int px = parent(x);
	int py = parent(y);

	if (px == py) return false;
	if (px < py) {
		pr[py] = px;
	}
	else {
		pr[px] = py;
	}
	return true;
}

// res[i][c] := i 文字目以降で最初に文字 c が登場する index (存在しないときは n)
vector<vector<int> > calcNext(const string& S) {
	int n = (int)S.size();
	vector<vector<int> > res(n + 1, vector<int>(26, n));
	for (int i = n - 1; i >= 0; --i) {
		for (int j = 0; j < 26; ++j) res[i][j] = res[i + 1][j];
		res[i][S[i] - 'a'] = i;
	}
	return res;
}
// mod 1000000007 の世界で a += b する関数
void add(long long& a, long long b) {
	a += b;
	if (a >= MOD) a -= MOD;
}

void solv() {
	ll n;
	cin >> n;
	ll a[60];
	for (size_t i = 0; i < n; i++)
		cin >> a[i];
	
	ll d[60];
	memset(d, 0, sizeof(d));
	ll v = 0;
	while (true)
	{
		bool under = true;
		for (size_t i = 0; i < n; i++)
		{
			ll va = a[i] + v + d[i];
			if (va >= n) {
				under = false;
			}
			ll div = (va / n);
			d[i] -= (div * n) + div;
			v += div;
		}
		if (under) break;
	}

	cout << v << endl;
}

int main() {
	//COMinit();
	solv();

	return 0;
}


Measured memory_bytes: 256
// Enjoy your stay.

#include <bits/stdc++.h>

#define EPS 1e-9
#define INF 1070000000LL
#define MOD 1000000007LL
#define fir first
#define foreach(it,X) for(auto it=(X).begin();it!=(X).end();it++)
#define ite iterator
#define mp make_pair
#define mt make_tuple
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define pb push_back
#define sec second
#define sz(x) ((int)(x).size())

using namespace std;

typedef istringstream iss;
typedef long long ll;
typedef pair<ll,ll> pi;
typedef stringstream sst;
typedef vector<ll> vi;

int m,n,obj[200];
int dp[180000];
int p3[12];

int f(int mask){
	int& res = dp[mask];
	if(res!=-1)return res;
	res = INF;

	int d[12];
	rep(i,m)d[i] = mask/p3[i]%3;

	int hit = 0;
	rep(i,n){
		int ok = 1;
		rep(j,m)if(d[j]!=2 && d[j] != (obj[i]>>j&1)){
			ok = 0;break;
		}
		if(ok)hit++;
		if(hit>1)break;
	}

	if(hit <= 1)return res = 0;
	rep(i,m)if(d[i] == 2){
		res = min(res, 1 + max(f(mask - 2 * p3[i]), f(mask - 1 * p3[i])));
	}

	return res;
}

int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	
	p3[0] = 1;
	rep(i,11)p3[i+1] = p3[i] * 3;
	while(cin>>m>>n && m){
		rep(i,n){
			string s;
			cin>>s;
			obj[i] = 0;
			rep(j,m)obj[i] |= (s[j] - '0')<<j;
		}
		memset(dp,-1,sizeof(dp));
		cout<<f(p3[m]-1)<<endl;
	}
}

Measured memory_bytes: 1924
a,b = map(int,input().split())
count = 0
if a >= b:
  count += a
  a = a - 1
else:
  count += b
  b = b - 1
if a >= b:
  count += a
  a = a - 1
else:
  count += b
  b = b - 1
print(count)

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

namespace AOJ_Practice
{
    class Program
    {
        static void Main(string[] args)
        {

            while (true)
            {
                var originStr = Console.ReadLine();
                if (originStr == "-")
                {
                    break;
                }

                var shuffleCount = int.Parse(Console.ReadLine());
                var builder = new StringBuilder(originStr);

                for (int i = 0; i < shuffleCount; i++)
                {
                    var shuffleStartIndex = int.Parse(Console.ReadLine());

                    var shuffleTopBuilder = new StringBuilder(builder.ToString());
                    var shuffleBottomBuilder = new StringBuilder(builder.ToString());

                    shuffleTopBuilder.Remove(0, shuffleStartIndex);
                    shuffleBottomBuilder.Remove(shuffleStartIndex, shuffleBottomBuilder.Length - shuffleStartIndex);

                    builder = new StringBuilder(shuffleTopBuilder.ToString() + shuffleBottomBuilder.ToString());
                }

                Console.WriteLine(builder.ToString());
            }
        }
    }
}



Measured memory_bytes: 17936
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file 
#include <ext/pb_ds/tree_policy.hpp> 
#include <functional> // for less 
#define pb push_back
#define For(i,s,e) for (ll i=(s); i<(e); i++)
#define Debug_array(a,n) for (ll i=(0); i<(n); i++) cout<<a[i]<<" "
#define Foe(i,s,e) for (ll i=(s); i<=(e); i++)
#define Fod(i,s,e) for (ll i=(s)-1; i>=(e); i--)
#define pii pair<ll,ll>
#define fi first
#define se second
#define endl "\n"
#define mp make_pair
#define big_prime 15486277
#define bigger_prime 179424697
#define biggest_prime 32416188691
//#define random_shuffle(indices.begin(), indices.end());
//std::random_device rd;
//std::mt19937 g(rd());
//std::shuffle(v.begin(), v.end(), g);
using namespace __gnu_pbds; 
using namespace std;
template <class T> ostream& operator << (ostream &os, const vector<T> &v) { for (T i : v) os << i << ' '; return os; }
template <class T> ostream& operator << (ostream &os, const set<T> &v) { for (T i : v) os << i << ' '; return os; }
template <class T, class S> ostream& operator << (ostream &os, const pair<T, S> &v) { os << v.first << ' ' << v.second; return os; }
// template <class T, class S> ostream& operator << (ostream &os, const unordered_map<T, S> &v) { for (auto i : v) os << '(' << i.first << "=>" << i.second << ')' << ' '; return os; }
 
#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
    template <class Arg1> void __f(const char* name, Arg1&& arg1) { cerr << name << " : " << arg1 << endl; }
    template <class Arg1, class... Args>
    void __f(const char* names, Arg1&& arg1, Args&&... args) {
        const char* sep = strchr(names + 1, ',');
        cerr.write(names, sep - names) << " : " << arg1 << "  ";
        __f(sep + 1, args...);
    }
#else
#define trace(...) 0
#define _CRT_SECURE_NO_WARNINGS
#endif // ifndef ONLINE_JUDGE


typedef long long ll;
typedef tree<ll, null_type, less<ll>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; 

#define Mod 1000000007
#define MAX 5002

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	ll n,d;cin>>n>>d;
	ll x = 2*d+1;
	ll ans = (n/x);
	if(n%x!=0) ans++;
	cout<<ans<<endl;































	
}

Measured memory_bytes: 256
import java.util.*;

public class Main {

    static class Edge {
        int from, to;

        public Edge(int from, int to) {
            this.from = from;
            this.to = to;
        }
    }

    static void dfs(int at, int prev) {
        if (visited[at]) return;
        visited[at] = true;
        if (prev != -1) counter[at] += counter[prev];

        List<Edge> edges = graph.get(at);
        for (Edge edge : edges) {
            if (visited[edge.to]) continue;
            dfs(edge.to, at);
        }
    }

    static int N;
    static int Q;
    static List<List<Edge>> graph;
    static long[] counter;
    static boolean[] visited;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = Integer.parseInt(sc.next()); 
        Q = Integer.parseInt(sc.next());
        visited = new boolean[N];
        Arrays.fill(visited, false);
        counter = new long[N];
        Arrays.fill(counter, 0);
        graph = new ArrayList<>();
        for (int i = 0; i < N; ++i) graph.add(new ArrayList<>());
        for (int i = 0; i < N-1; ++i) {
            int a = Integer.parseInt(sc.next()) - 1;
            int b = Integer.parseInt(sc.next()) - 1;
            graph.get(a).add((new Edge(a, b)));
            graph.get(b).add((new Edge(b, a)));
        }

        for (int i = 0; i < Q; ++i) {
            int id = Integer.parseInt(sc.next()) - 1;
            long x = Integer.parseInt(sc.next());
            counter[id] += x;
        }

        dfs(0, -1);

        for (int i = 0; i < N; ++i)
            System.out.print(counter[i] + " ");
        System.out.println();
    }
}

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

using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 110000;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << setiosflags(ios::fixed) << setprecision(12);
    ll n, m;
    cin >> n >> m;
    vector<int> a(n + 1);
    ll sum = 0;
    for (int i = 1; i <= m; i++)
    {
        ll t;
        cin >> t;
        sum += t;
    }
    if (n >= sum)
        cout << n - sum << "\n";
    else
        cout << -1 << "\n";
    return 0;
}

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

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
#include<bits/stdc++.h>
using namespace std;
template<class T> T read(){
	T x=0,w=1;char c=getchar();
	for(;!isdigit(c);c=getchar())if(c=='-') w=-w;
	for(;isdigit(c);c=getchar()) x=x*10+c-'0';
	return x*w;
}
template<class T> T read(T&x){
	return x=read<T>();
}
#define CO const
#define IN inline
typedef long long LL;

CO int mod=1000000000+7;
IN int add(int a,int b){
	return (a+=b)>=mod?a-mod:a;
}
IN int mul(int a,int b){
	return (LL)a*b%mod;
}
IN int fpow(int a,int b){
	int ans=1;
	for(;b;b>>=1,a=mul(a,a))
		if(b&1) ans=mul(ans,a);
	return ans;
}

CO int N=200000+10;
int lst[N],dp[N];

int main(){
	int n=read<int>();
	dp[0]=1;
	for(int i=1;i<=n;++i){
		int val=read<int>();
		dp[i]=dp[i-1];
		if(lst[val] and lst[val]<i-1) dp[i]=add(dp[i],dp[lst[val]]);
		lst[val]=i;
	}
	printf("%d\n",dp[n]);
	return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std ;
#define int long long
int32_t main() {
    int n ;
    cin >> n ;
    vector<int> v(n) ;
    for(auto &X : v) cin >> X ;
    int maxx = v[0];
    int ans = 0 ;
    for (int i = 1 ; i < n ; i++ ) {
        if (maxx > v[i]) {
            ans += ( maxx - v[i] ) ;
        }
        else {
            maxx = v[i] ;
        }
    }
    cout << ans << endl ;
}

Measured memory_bytes: 4820
#include<bits/stdc++.h>
using namespace std;
int que[50];
int n,k;
int ans;
bool cmp(int x,int y)
{
	return x>y;
}
int main()
{
	ios::sync_with_stdio(0);
	cin>>n>>k;
	for(int i=0;i<n;i++)
		cin>>que[i];
	sort(que,que+n,cmp);
	for(int i=0;i<k;i++)
		ans+=que[i];
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
mod = 998244353

# mod mでの二項係数を求める
class BiCoeff(object):
    def __init__(self, MAX, m):
        super(BiCoeff, self).__init__()
        fac = [0]*MAX
        finv = [0]*MAX
        inv = [0]*MAX

        fac[0] = 1
        fac[1] = 1
        finv[0] = 1
        finv[1] = 1
        inv[1] = 1
        for i in range(2,MAX):
            fac[i] = (fac[i-1]*i)%m
            inv[i] = m - (inv[m%i] * (m//i))%m
            finv[i] = (finv[i-1] * inv[i])%m

        self.MAX = MAX
        self.m = m
        self.fac = fac
        self.finv = finv
        self.inv = inv

    def calc(self,n,k):
        if n<k:
            return 0
        if n<0 or k<0:
            return 0
        return (self.fac[n] * (self.finv[k]*self.finv[n-k])%self.m)%self.m

n,m,k = map(int, input().split())

bicoeff = BiCoeff(10**6, mod)

res = 0
for ki in range(k+1):
    r = bicoeff.calc(n-1, ki)
    if ki==0:
        r = 1
    x = n - ki
    # print(ki, r, x, m * pow(m-1, x-1, mod))
    res += r * m * pow(m-1, x-1, mod)
    res %= mod
print(res)

Measured memory_bytes: 127668
#include<stdio.h>
int main(){
    int i,n,k,q,m;
    scanf("%d %d %d",&n,&k,&q);
    int a[n],b[q];
    for(i=0;i<q;i++){
        scanf("%d",&b[i]);
    }
    for(i=0;i<n;i++){
        a[i]=k-q;
    }
    for(i=0;i<q;i++){
        m=b[i]-1;
        a[m]++;
    }
    for(i=0;i<n;i++){
        if(a[i]>0){
            printf("Yes\n");
        }
        else{
            printf("No\n");
        }
    }
}

Measured memory_bytes: 1280
from queue import Queue
Sa, Sb, Sc = Queue(), Queue(), Queue()
for c in input(): Sa.put(c)
for c in input(): Sb.put(c)
for c in input(): Sc.put(c)

S = Sa
d1 = {'a': Sa, 'b': Sb, 'c': Sc}
d2 = {Sa: 'A', Sb: 'B', Sc:'C'}
while not S.empty():
    S = d1[S.get()]
print(d2[S])


Measured memory_bytes: 3952
#include<iostream>
typedef long long ll;

using namespace std;

int main()
{
    ll a[6],i;
    for(i=1; i<=5; i++)
        cin>>a[i];
    for(i=1; i<=5; i++)
    {
        if(a[i]==0)
        {
            cout<<i<<endl;
            break;
        }
    }
}




Measured memory_bytes: 3152
//c++ -std=gnu++14 a.cpp
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <iostream>
#include <istream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <tuple>
#include <iomanip>
#include <climits>
#include <fstream>
#include <random>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
//typedef pair<ll, ll> P;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define revrep(i, n) for(int i = (n)-1; i >= 0; i--)
#define pb push_back
#define f first
#define s second
#define chmin(x, y) x = min(x, y);
#define chmax(x, y) x = max(x, y);
#define sz(x) ((int)(x).size())

//const ll INFL = LLONG_MAX;//10^18 = 2^60
const ll INFL = 1LL<<60;
//const int INF = INT_MAX;
const int INF = 1 << 30;//10^9
const ll MOD = 1000000007;
//const ll MOD = 998244353;
double EPS = 1e-10;

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

void pres(double A){printf("%.9lf\n", A);}
void BinarySay(ll x, ll y = 60){rep(i, y) cout << (x>>(y-1-i) & 1); cout << endl;}
ll cnt_bit(ll x){return __builtin_popcountll(x);}

ll pow_long(ll x, ll k){
  ll res = 1;
  while(k > 0){
    if(k % 2) res *= x;
    x *= x; k /= 2;
  }
  return res;
}

ll pow_mod(ll x, ll k){
  ll res = 1;
  while(k > 0){
    if(k % 2){
      res *= x; res %= MOD;
    }
    x *= x; x %= MOD;
    k /= 2;
  }
  return res;
}

ll inverse(ll x){return pow_mod(x, MOD - 2);};

ll gcd(ll a, ll b){
    if(b == 0) return a;
    return gcd(b, a % b);
}

ll lcm(ll x, ll y){
  ll res = x / gcd(x, y);
  res *= y;
  return res;
};


//コンビネーション
const int MAXcomb = 2000010;
ll fac[MAXcomb], finv[MAXcomb], inv[MAXcomb];
//facはn!,finvは1/n!
//invは逆元
void COMinit(){
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(int i = 2; i < MAXcomb; i++){
        fac[i] = fac[i-1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;
        finv[i] = finv[i-1] * inv[i] % MOD;
    }
}
ll comb(int n, int k){
    if(n < k) return 0;
    if(n < 0 || k < 0) return 0;
    return fac[n] * finv[k] % MOD * finv[n-k] % MOD;
}

const int MAXkai = 500010;
ll kai_memo[MAXkai];
ll kai(ll N){
  if(kai_memo[N] != 0) return kai_memo[N];
  if(N <= 1) return 1;
  return kai_memo[N] = N * kai(N-1) % MOD;
}

ll disit(ll s, ll base = 10){
  ll res = 0;
  while(s){
    res++;
    s /= base;
  }
  return res;
}

bool ok(int I, int J, vector<vector<char>> C, int h, int w, int k){
  int cnt = 0;
  rep(i, h)rep(j, w){
    if((I>>i)&1 || (J>>j)&1) continue;
    if(C[i][j] == '#') cnt++;
  }
  return cnt == k;
}

void solve(){
  int h, w, k;
  cin >> h >> w >> k;
  vector<vector<char>> C(h, vector<char>(w));
  rep(i, h)rep(j, w){
    char c;
    cin >> c;
    C[i][j] = c;
  }
  int ans = 0;
  rep(i, 1<<h)rep(j, 1<<w){
    ans += ok(i, j, C, h, w, k);
  }
  cout << ans << endl;
}


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


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

int main() {
	int n, k, ans=1;
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		if (ans > k) {
			ans += k;
		}
		else {
			ans *= 2;
		}
	}
	cout << ans << endl;




	return 0;
}

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

#define int long long
#define pb emplace_back
#define mp make_pair
#define f(i,a,n) for(int i=a ; i<n ; i++)
#define F first
#define S second
#define fast ios:: sync_with_stdio(false),cin.tie(0);


int32_t main(){
	fast;
	int a,b,h;
	cin >> a >> b >> h;
	
	cout << (a+b)*h/2;
}







Measured memory_bytes: 256
from collections import Counter
import math
def main():
    n = int(input())
    ans = []
    for x in range(1, int(math.sqrt(n+1))+1):
        for y in range(1, int((math.sqrt(n+1)))+1):
            for z in range(1, int((math.sqrt(n+1)))+1):
                ans.append(x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x)
    counter = Counter(ans)
    for i in range(1, n+1):
        print(counter[i])
 
 
if __name__ == '__main__':
    main()

Measured memory_bytes: 50604
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ld long double
#define al(a) (a).begin(),(a).end()
#define mk make_pair
#define check cout<<"?"<<endl;

ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;

int main() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    int n,dis; cin>>n;
    map<int,int> me;
    int ad;
    rep(i,n+1){
        cin>>ad;
        if(me.count(ad)){
            dis=i-me[ad]+1; break;
        }
        else{
            me[ad]=i;
        }
    }
    vector<ll> v(n+2,0); v[1]=1;
    for(int i=2;i<=n+1;i++){
        v[i]=(-v[MOD%i]*(MOD/i))%MOD;
    }
    ll c=1,d=1;
    rep(i,n+1){
        c=((c*(n+1-i))%MOD)*v[i+1]%MOD;
        c=(c+MOD)%MOD;
        cout<<(c-d+MOD)%MOD<<endl;
        d=((d*(n+1-dis-i))%MOD)*v[i+1]%MOD;
        d=(d+MOD)%MOD;
    }
}

Measured memory_bytes: 6656
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

int a, b, x, v;
int main() {
	cin >> a >> b >> x;
	double pi = acos(-1.0);
	v = a * a * b;
	if(v < 2*x) {
		printf("%.9f", atan(2.0 * (v-x) / (a*a*a)) / pi * 180);
	} else {
		printf("%.9f", 90 - atan(2.0 * x / (b*b*a)) / pi * 180);
	}
    return 0;
}

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

int main(){
	std::string t;
	std::cin >> t;
	int tz = t.size();
	int res = 0;
	for(int i=0; i<tz; i++){
		if(t[i] == '?'){
			t[i] = 'D';
		}
	}
	std::cout << t << std::endl;
	return 0;
}

Measured memory_bytes: 3720
#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define FORR(i,a,b) for (int i=(a);i>=(b);i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pcnt __builtin_popcount
#define sz(x) (int)(x).size()
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define show(x) cout<<#x<<" = "<<x<<endl;
#define rng(a) (a.begin()),(a.end())
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef set<int> si;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pll> vpll;
typedef set<ll> sl;
typedef __int128_t lll;
typedef pair<lll,lll> plll;
typedef vector<lll> vlll;
template<typename T>string join(vector<T>&v){stringstream s;FOR(i,0,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename A,size_t N,typename T>void Fill(A (&array)[N],const T&v){fill((T*)array,(T*)(array+N),v);}
lll gcd(lll a,lll b,lll &x,lll &y){if(!b){x=1;y=0;return a;}lll d=gcd(b,a%b,y,x);y-=a/b*x;return d;}
ll gcd(ll a,ll b){lll x=0,y=0;return gcd(a,b,x,y);}
ll modpow(lll a,lll n,ll m){if(!a)return a;lll p=1;for(;n>0;n>>=1,a=a*a%m)if(n&1)p=p*a%m;return(ll)p;}
void dout(double d){printf("%.12f\n",d);}
void YN(bool z){cout<<(z?"YES\n":"NO\n");}
void Yn(bool z){cout<<(z?"Yes\n":"No\n");}
void yn(bool z){cout<<(z?"yes\n":"no\n");}

const int iinf = 1e9+1;
const ll linf = 1e18;
const int mod = 1e9+7;
const double pi = acos(-1);
const double eps = 1e-10;
const int N = 2e5;
ll n, x, y, mama, mami=iinf, mima, mimi=iinf, c[N], zc;
map<ll, vl> m;
main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> n;
  FOR(i, 0, n){
    cin >> x >> y;
    if(x > y) swap(x, y);
    maxs(mama, y);
    mins(mami, y);
    maxs(mima, x);
    mins(mimi, x);
    m[x].pb(i);
    m[y].pb(i);
  }
  ll ans = iinf;
  zc = n;
  map<ll, vl>::iterator l=m.begin(), r=m.begin();
  while(r != m.end()){
    each(itr, r->se) if(++c[*itr] == 1) zc--;
    while(!zc){
      mins(ans, r->fi - l->fi);
      each(itr, l->se) if(--c[*itr] == 0) zc++;
      l++;
    }
    r++;
  }
  cout << min((mama-mami) * (mima-mimi), ans * (mama-mimi)) << endl;
  return 0;
}

Measured memory_bytes: 45568
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
//const int INF = 1e8;
using namespace std;

string ans;

void dfs(string s, int cul, int i){
	if(i == 7){
		if(cul == 7){
			ans = s;
		}
		return;
	}

	s[i] = '+';
	dfs(s, cul + (s[i + 1] - '0'), i + 2);
	s[i] = '-';
	dfs(s, cul - (s[i + 1] - '0'), i + 2);
}

int main(){
	char a;
	string s = "a+b+c+d=7";
	rep(i,4){
		cin >> a;
		s[i * 2] = a;
	}

	dfs(s,s[0] - '0',1);
	cout << ans << endl;
}


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

// macros
#define overload_rep(va_0, va_1, va_2, va_3, name, ...) name
#define rep_0_(i, n) for(int i = 0; i < (n); ++i)
#define rep_1_(i, x, y) for(int i = (x); i <= (y); ++i)
#define rep_2_(i, x, y, z) for(int i = (x); i >= (y); --i)
#define rep(...) overload_rep(__VA_ARGS__, rep_2_, rep_1_, rep_0_)(__VA_ARGS__)
#define all(a) a.begin(), a.end()
#ifndef STOP_DEBUG
#define debug(...)\
    do { cerr << boolalpha << "[" << #__VA_ARGS__ << "]:";\
    debug_cerr(__VA_ARGS__); cerr << noboolalpha; } while (0)
#else
#define debug(...)
#endif

// functions
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
void debug_cerr(){ cerr << '\n'; }
template<class Head, class... Tail>
void debug_cerr(Head head, Tail... tail){
    cerr << ' ' << head;
    debug_cerr(tail...);
}

// cin/cout setup
struct IoSetup{
    IoSetup(){
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);
    }
} iosetup;

// libraries

// declarations
int N, T;
int dp[3001][6001];
pair<int, int> product[3000];

// solve
int main(){

    cin >> N >> T;
    rep(i, N)cin >> product[i].first >> product[i].second;
    sort(product, product + N);

    rep(i, N){
        int a, b;
        tie(a, b) = product[i];
        rep(j, T){
            chmax(dp[i + 1][j], dp[i][j]);
            chmax(dp[i + 1][j + a], dp[i][j] + b);
        }
        rep(j, T, 6000)chmax(dp[i + 1][j], dp[i][j]);
    }    

    int ans = 0;
    rep(j, 0, 6000)chmax(ans, dp[N][j]);
    cout << ans << '\n';
    return 0;

}


Measured memory_bytes: 69760
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n, p, t=0;
	cin >> n;
	p=n;
	while (p!=0)
	{
		t+=p%10;
		p/=10;
	}
	if (n%t==0) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python
from collections import defaultdict

N = int(input())

ab = []
for _ in range(N - 1):
    ab.append(tuple(map(int, input().split())))
c = sorted(list(map(int, input().split())), reverse=True)

nodes = defaultdict(set)
for a, b in ab:
    nodes[a].add(b)
    nodes[b].add(a)

d = {}
done = set()
stack = [1]
ci = 0
node = 1
while stack:
    node = stack.pop()
    d[node] = c[ci]
    stack += list(nodes[node] - done)
    done.add(node)
    ci += 1

print(sum(c[1:]))
for i in range(N):
    print(d[i + 1], end=' ')
print()



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

#define REP(i, n) for(int i = 0; i != n; ++i)
#define REPR(i, n) for(int i = n - 1; i != -1; --i)
#define FOR(i, a, b) for(int i = a; i != b; ++i)
#define RBF(i, n) for(auto &i : n)
#define ABS(n) (n < 0 ? -n : n)
#define MIN(a, b) (a < b ? a : b)
#define MAX(a, b) (a > b ? a : b)
#define IN(n) (cin >> n)
#define OUT(n) (cout << n << "\n")
#define INF 1e9
#define ALL(v) (v).begin(), (v).end()
#define V vector<int>

using namespace std;
using ll = long long;

int main() {
    int a;
    string s;
    IN(a);
    IN(s);
    // 重い
    if(a >= 3200) OUT(s);
    else OUT("red");
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define PRINT(s) cout << s << endl;
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define REP(i, n) FOR((i), 0, (n))

int main() {
    int n, y;
    cin >> n >> y;
    int minLimit = n * 1000;
    int maxLimit = n * 10000;
    if (y < minLimit || maxLimit < y) {
        cout << -1 << " " << -1 << " " << -1 << endl;
        return 0;
    }
    REP(yukichi, n + 1) {
        int currentYukichi = 10000 * yukichi;
        if (currentYukichi > y) continue;
        REP(higuchi, n + 1) { 
            int noguchi = n - (yukichi + higuchi);
            if (noguchi < 0) continue;
            int currentHiguchi = 5000 * higuchi;
            if (currentYukichi + currentHiguchi + (1000 * noguchi) != y) continue;
            cout << yukichi << " " << higuchi << " " << noguchi << endl;
            return 0;
        }
    }
    cout << -1 << " " << -1 << " " << -1 << endl;
    return 0;

}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
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()
{
  int n,m,x; cin >> n >> m >> x;
  vector<int> c(n);
  vector<vector<int>> a(n, vector<int>(m));
  rep(i,n) {
    cin >> c[i];
    rep(j,m) cin >> a[i][j];
  }

  int res = 1e+9;
  rep(mask, (1 << n)) {
    vector<int> vec(m, 0);
    int sum = 0;
    rep(j,n) {
      if((mask >> j) & 1) {
	sum += c[j];
	rep(k,m) {
	  vec[k] += a[j][k];
	}
      }
    }
    bool f = true;
    rep(k,m) {
      if(vec[k] < x) {
	f = false;
	break;
      }
    }
    if(f) chmin(res, sum); 
  }

  if(res == 1e+9) cout << -1 << "\n";
  else cout << res << "\n";
  
  return 0;
}


Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define mp make_pair
#define PI pair<int,int>
#define For(i,l,r) for(int i=(int)(l);i<=(int)(r);i++)
#define Rep(i,r,l) for(int i=(int)(r);i>=(int)(l);i--)
#define pb push_back
#define fi first
#define se second
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline ll read(){
	ll x = 0; char ch = gc(); bool positive = 1;
	for (; !isdigit(ch); ch = gc())	if (ch == '-')	positive = 0;
	for (; isdigit(ch); ch = gc())	x = x * 10 + ch - '0';
	return positive ? x : -x;
}
inline void write(ll a){
    if(a<0){
    	a=-a; putchar('-');
	}
    if(a>=10)write(a/10);
    putchar('0'+a%10);
}
inline void writeln(ll a){write(a); puts("");}
inline void wri(ll a){write(a); putchar(' ');}
inline ull rnd(){
	return ((ull)rand()<<30^rand())<<4|rand()%4;
}
const int N=200005,mod=1000000007;
ll ksm(ll a,int b){
	int ans=1;
	for(;b;b>>=1){
		if(b&1)ans=ans*a%mod;
		a=a*a%mod;
	}
	return ans;
}
ll fac[N],f[N],ni[N];
char ch[N];
int q[N];
ll c(int a,int b){
	return a>=b&&b>=0?fac[a]*ni[b]%mod*ni[a-b]%mod:0;
}
int main(){
	//freopen("std.in","r",stdin); freopen("my.out","w",stdout);
	For(i,fac[0]=1,N-1)fac[i]=fac[i-1]*i%mod; ni[N-1]=ksm(fac[N-1],mod-2);
	Rep(i,N-1,1)ni[i-1]=ni[i]*i%mod;
	int n=read(),m=read();
	scanf("%s",ch+1);
	if(ch[1]=='B')For(i,1,m)ch[i]='R'+'B'-ch[i];
	int fr=1;
	For(i,2,m)if(ch[i]!=ch[i-1])fr=0;
	if(fr){
		ll ans=0;
		For(i,1,n)ans=(ans+c(i-1,n-i)+2*c(i-1,n-i-1))%mod;
		writeln(ans);
		return 0;
	}
	int cnt=0,mx=1e9,fff=1;
	For(i,1,m){
		if(ch[i]=='B'){
			if(cnt&1)mx=min(mx,cnt); else if(fff)mx=min(mx,cnt+1);
			cnt=0; fff=0;
		}else cnt++;
	}
	if(n&1){
		puts("0"); return 0;
	}
	int t=mx; 
	mx/=2; mx+=2;  //cout<<mx<<endl;
	static ll ans[N];
	ans[0]=1;
	For(i,1,n){
		if(i==1)ans[i]=-1; else ans[i]=0;
		ans[i]=(ans[i]+(ll)ans[i-1]*2)%mod;
		if(i>=mx)ans[i]=(ans[i]-ans[i-mx])%mod;
	}
	//For(i,0,n)cout<<ans[i]<<" ";puts("");
	ll sum=0;
	for(int i=1;i<=t&&i<n;i+=2){
		sum=(sum+(i+1)*ans[(n-i-1)/2])%mod;// cout<<(i+1)<<" "<<ans[(n-i-1)/2]<<endl;
	}
	cout<<(sum+mod)%mod<<endl;
}
/*
200000 8
RRBRRRRB

*/

Measured memory_bytes: 6656
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(I,A,B) for(ll I = ll(A); I < ll(B); ++I)
 
 
int main(){
	ll n,q,k;
	cin >> n;
	set<ll> se;
	FOR(i,0,n){
		cin>>k;
		se.insert(k);
	}
	cin >> q;
	FOR(i,0,q){
		cin >> k;
		cout << se.count(k) << endl;
	}
}


Measured memory_bytes: 7784
#include <stdio.h>

int main()
{
	int n,i,a;
	int S[13]={0};
	int H[13]={0};
	int C[13]={0};
	int D[13]={0};
	char m;
	
	scanf("%d\n",&n);
	
	for(i=0;i<n;i++){
		scanf("%c %d\n",&m,&a);
		
		if(m=='S')
			S[a-1]=1;
		else if(m=='H')
			H[a-1]=1;
		else if(m=='C')
			C[a-1]=1;
		else if(m=='D')
			D[a-1]=1;
			
	}
	
	for(i=0;i<13;i++)
		if(S[i]==0)
			printf("S %d\n",i+1);
			
	for(i=0;i<13;i++)
		if(H[i]==0)
			printf("H %d\n",i+1);
			
	for(i=0;i<13;i++)
		if(C[i]==0)
			printf("C %d\n",i+1);
			
	for(i=0;i<13;i++)
		if(D[i]==0)
			printf("D %d\n",i+1);
			
	return 0;
	
}


Measured memory_bytes: 2016
#include<stdio.h>
int main(){
  int N=0,i=0,j=0,count=0;
  int A[10000];
  scanf("%d",&N);
  for(i=0;i<N;i++){
    scanf("%d",&A[i]);
  }
  count=selsort(A,N);
  if(N>1){
    for(i=0;i<N;i++){
      if(i<N-1){
	printf("%d ",A[i]);
      }
      if(i==N-1){
	printf("%d",A[i]);
      }
    }
    printf("\n");
    printf("%d\n",count);
  }
  else {
    for(i=0;i<N;i++){
      printf("%d",A[i]);
    }
    printf("\n");
    printf("%d\n",count);
  }
  return 0;
}
int selsort(int A[], int N){
  int i=0,j=0,temp=0;
  int min=0;
  int count=0;
  for(i=0;i<=N-1;i++){
    min=i;
    for(j=i;j<=N-1;j++){
      if(A[j]<A[min]){
	min=j;
      }
    }
    temp=A[i];
    A[i]=A[min];
    A[min]=temp;
    if(i!=min)count++;
  }
  return count;
}



Measured memory_bytes: 2140
N, M = map(int, input().split())
lightList = []
for _ in range(M):
    lightList.append(list(map(int, input().split())))
P = list(map(int, input().split()))

ans = 0
for i in range(2**N):
    flag = True
    for a in range(M):
        cnt = 0
        for b in lightList[a][1:]:
            if (1 & (i>>(b-1))):
                cnt += 1
        if cnt % 2 != P[a]:
            flag = False
    if flag:
        ans += 1
print(ans)


Measured memory_bytes: 3064
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    Q = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    low=[]
    high=[]
    s1=s2=0
    btot=0
    for _ in range(Q):
        q=list(map(int, input().split()))
        if q[0]==1:
            a,b=q[1:]
            btot+=b
            if not low:
                heappush(low,-a)
                s1+=a
                continue
            if a>-low[0]:
                heappush(high,a)
                s2+=a
                if len(low)<len(high):
                    a2=heappop(high)
                    heappush(low,-a2)
                    s2-=a2
                    s1+=a2
            else:
                heappush(low,-a)
                s1+=a
                if len(high)+1<len(low):
                    a2=-heappop(low)
                    heappush(high,a2)
                    s1-=a2
                    s2+=a2
        else:
            if len(low)==0:
                print(0)
                continue
            ans=btot
            mid=-low[0]
            ans+=len(low)*mid-s1-len(high)*mid+s2
            print(mid,round(ans))

if __name__ == "__main__":
    main()

Measured memory_bytes: 87028
using System;
    class Program
    {
        static void Main(string[] args)
        {
            string S = Console.ReadLine();
            string T = Console.ReadLine();

            if(S.Length != T.Length)
            {
                Console.WriteLine("No");
                return;
            }

            for(int i = 0; i < S.Length; i++)
            {
                if(S == T)
                {
                    Console.WriteLine("Yes");
                    return;
                }
                char c = S[0];
                S = S.Substring(1) + c.ToString();
            }
            Console.WriteLine("No");
        }
    }

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

using namespace std;

int main(){
  vector<vector<char>> V(2,vector<char>(3,0));
  for(int i = 0; i < 2; i++){
    for(int j = 0; j < 3; j++) cin >> V[i][j];
  }
  if(V[0][0] == V[1][2] && V[0][1] == V[1][1] && V[0][2] == V[1][0]) cout << "YES";
  else cout << "NO";
}


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

using namespace std;
int main(){
    int n; cin>>n;
    int a[n];
    int ans=0;
    long long res=0;;
  for(int i=0;i<n;i++) cin>>a[i];
  for(int i=0;i<n;i++){
    ans=max(ans,a[i]);
    res+=ans-a[i];
    }
  cout<<res;
  return 0;
}

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

int main()
{
  int h,n,sum;
  sum=0;
  cin>>h>>n;
  vector<int> atk(n);
  for(int i=0;i<n;i++)
  {
    cin>>atk.at(i);
    sum+=atk.at(i);
  }
  if(h>sum)
    cout<<"No"<<endl;
  else
    cout<<"Yes"<<endl;  
}

Measured memory_bytes: 3716
#include <stdio.h>
#include <stdlib.h>
#define NIL -1

typedef struct{
  int parent;
  int left;  //左の子
  int right; //右の兄弟
}Node;

int getDepth(Node**, int);

main(){
  int n, i, j, k, id, child, child_, depth;
  Node **nodes;

  scanf("%d", &n);
  nodes = (Node**)malloc(sizeof(Node*)*n);
  for(i=0; i<n; i++){
    nodes[i] = (Node*)malloc(sizeof(Node));
    nodes[i]->parent = NIL;
    nodes[i]->left = NIL;
    nodes[i]->right = NIL;
  }

  for(i=0; i<n; i++){
    scanf("%d", &id);
    scanf("%d", &k);
    for(j=0; j<k; j++){
      scanf("%d", &child);
      nodes[child]->parent = id;
      if(j==0) nodes[id]->left = child;
      if(j>0) nodes[child_]->right = child;
      child_ = child;
    }
  }

  for(i=0; i<n; i++){
    depth = getDepth(nodes, i);
    printf("node %d: parent = %d, depth = %d, ",i, nodes[i]->parent, depth);
    
    if(depth == 0) printf("root, [");
    else if(nodes[i]->left == NIL) printf("leaf, [");
    else printf("internal node, [");

    for(j = nodes[i]->left; j != NIL;){
      printf("%d", j);
      j = nodes[j]->right;
      if(j != NIL) printf(", ");
    }

    printf("]\n");
  }

  return 0;
}

int getDepth(Node **nodes, int p){
  if(nodes[p]->parent == NIL) return 0;
  else{
    return 1 + getDepth(nodes, nodes[p]->parent);
  }
}

Measured memory_bytes: 4520