akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class AtCoderE
{
    static void Main()
    {
        var sc = new Scanner();

        int n = sc.NextInt();
        int k = sc.NextInt();
        long mod = 1000000007;

        long[] patterns = new long[k + 1];

        long answer = 0;
        for (int i = k; i >= 1; i--)
        {
            long pattern = Pow(k / i, n, mod);
            for (int j = i + i; j <= k; j += i)
            {
                pattern -= patterns[j];
                if (pattern < 0)
                {
                    pattern += mod;
                }
            }
            patterns[i] = pattern;
            answer = (answer + (i * pattern % mod)) % mod;
        }

        Console.WriteLine(answer);
    }

    // 掛け算（mod版）
    private static long Mul(long a, long b, long c)
    {
        return ((a % c) * (b % c)) % c;
    }

    // 割り算（mod版）
    private static long Div(long a, long b, long c)
    {
        return Mul(a, Pow(b, c - 2, c), c);
    }

    // べき乗（mod版）
    private static long Pow(long a, long b, long c)
    {
        if (b == 0)
        {
            return 1;
        }
        else if (b == 1)
        {
            return a % c;
        }
        else if (b % 2 == 0)
        {
            long d = Pow(a, b / 2, c);
            return d * d % c;
        }
        else
        {
            return a * Pow(a, b - 1, c) % c;
        }
    }

    class Scanner
    {
        private string[] _line;
        private int _index;
        private const char Separator = ' ';

        public Scanner()
        {
            _line = new string[0];
            _index = 0;
        }

        public string Next()
        {
            while (_index >= _line.Length)
            {
                _line = Console.ReadLine().Split(Separator);
                _index = 0;
            }

            return _line[_index++];
        }

        public int NextInt() => int.Parse(Next());
        public long NextLong() => long.Parse(Next());
        public double NextDouble() => double.Parse(Next());
        public decimal NextDecimal() => decimal.Parse(Next());
        public char NextChar() => Next()[0];
        public char[] NextCharArray() => Next().ToCharArray();

        public string[] Array()
        {
            _line = Console.ReadLine().Split(Separator);
            _index = _line.Length;
            return _line;
        }

        public int[] IntArray() => Array().Select(int.Parse).ToArray();
        public long[] LongArray() => Array().Select(long.Parse).ToArray();
        public double[] DoubleArray() => Array().Select(double.Parse).ToArray();
        public decimal[] DecimalArray() => Array().Select(decimal.Parse).ToArray();
    }
}

Measured memory_bytes: 28120
#include<stdio.h>

int main(){
    int a, b, c, p, i;
    while(scanf("%d %d %d", &a, &b, &c), a | b | c){
	int m;
	if(a >= b && a >= c)m = b * b + c * c;
	if(b >= a && b >= c)m = a * a + c * c;
	if(c >= a && c >= b)m = a * a + b * b;
	scanf("%d", &p);
	for(i = 0;i < p;i++){
	    scanf("%d", &a);
	    if(a * a * 4 > m)puts("OK");
	    else puts("NA");
	}
    }
    return 0;
}

Measured memory_bytes: 1012
import sys, math
from functools import lru_cache
sys.setrecursionlimit(10**9)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

Q, H, S, D = mi()
N = ii()

x = min(
    8*Q, 6*Q+H, 4*Q+2*H, 2*Q+3*H, 4*H,
    4*Q+S, 2*Q+H+S, 2*H+S, 2*S, D
)
y = min(4*Q, 2*Q+H, 2*H, S)

if N%2 == 0:
    print(x*(N//2))
else:
    print(x*(N//2)+y)




Measured memory_bytes: 9380
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
typedef long long ll;
#define MOD 998244353
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<ll>> d(n, vector<ll>(n, LLONG_MAX / 2000));
    for(int i = 0; i < n; i++) {
        d[i][i] = 0;
    }
    for(int i = 0; i < m; i++) {
        ll a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        d[a][b] = -c;
    }
    for(int i = 0; i < n; i++) {         // 経由する頂点
        for(int j = 0; j < n; j++) {     // 開始頂点
            for(int k = 0; k < n; k++) { // 終端
                d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
            }
        }
    }
    if(d[0][0] == 0) {
        cout << -d[0][n - 1] << endl;
    } else {
        cout << "inf" << endl;
    }
}

Measured memory_bytes: 10112
k=int(input())
a=[]
for i in range(1,10):
    a.append(i)
s=0
t=8
for i in range(1,10):
    for j in range(s,t+1):
        if str(a[j])[len(str(a[j]))-1]=="0":
            a.append(str(a[j])+"0")
            a.append(str(a[j])+"1")
        elif str(a[j])[len(str(a[j]))-1]=="9":
            a.append(str(a[j])+"8")
            a.append(str(a[j])+"9")
        else:
            c=int(str(a[j])[len(str(a[j]))-1])-1
            d=int(str(a[j])[len(str(a[j]))-1])
            e=int(str(a[j])[len(str(a[j]))-1])+1
            a.append(str(a[j])+str(c))
            a.append(str(a[j])+str(d))
            a.append(str(a[j])+str(e))
    s=t+1
    t=len(a)-1
print(a[k-1])

Measured memory_bytes: 93328
n = int(input())
vals  = []
for i in range(n):
  vals.append(list(map(int,input().split())))

dp = [[0]*3 for i in range(n)]

dp[0][1] = vals[0][1]
dp[0][2] = vals[0][2]
dp[0][0] = vals[0][0]

for i in range(1, n):
  dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]) + vals[i][0]
  dp[i][1] = max(dp[i - 1][0], dp[i - 1][2]) + vals[i][1]
  dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]) + vals[i][2]

print(max(dp[n-1][0], dp[n-1][1], dp[n-1][2]))

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

class Main {

    static int dec(char c, int i) {
        if (c == 'X') {
            return i;
        } else {
            return (int) (c - '0');
        }
    }

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

        while((line = br.readLine()) != null){
            String[] input = line.split("[+=]");
            int limit = 0;
            if((input[0].charAt(0) == 'X' && input[0].length() != 1) ||
            (input[1].charAt(0) == 'X' && input[1].length() != 1) ||
            (input[2].charAt(0) == 'X' && input[2].length() != 1)){
                limit = 1;
            }
            StringBuilder a = new StringBuilder();
            StringBuilder b = new StringBuilder();

            for(int i = 0; i < input[2].length()-input[0].length(); i++){
                a.append("0");
            }   
            a.append(input[0]);
            input[0] = a.toString();

            for(int i = 0; i < input[2].length()-input[1].length(); i++){
                b.append("0");
            }            
            b.append(input[1]);
            input[1] = b.toString();
            
            boolean result = false;
            int ans;
            int carry = 0;

            large:
            for(ans = 9; ans >= limit; ans--){
                carry = 0;
                for(int j = input[2].length() - 1; j >= 0; j--){
                    int m = dec(input[0].charAt(j) , ans);
                    int n = dec(input[1].charAt(j) , ans);
                    int o = dec(input[2].charAt(j) , ans);
                    if((m + n + carry) % 10 != o){
                        continue large;
                    }
                    carry = (m+n+carry)/10;
                }
                result = true;
                break;
            }
            
            if(result && carry == 0){
                System.out.println(ans);
            }else{
                System.out.println("NA");
            }
        }
    }
}


Measured memory_bytes: 25088
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i) = 0; (i) < (n); ++(i))
#define rrep(i,n) for(int (i) = (n) - 1; (i) >= 0; --(i)) //Reversi rep
#define nfor(i,a,b) for(int (i) = (a); (i) < (b); ++(i)) //Natural for
#define rfor(i,a,b) for(int (i) = (b) - 1; (i) >= (a); --(i)) //Reversi for
#define ll long long
#define mod (1000000007)
#define YES cout << "YES" << endl;
#define Yes cout << "Yes" << endl;
#define yes cout << "yes" << endl;
#define NO cout << "NO" << endl;
#define No cout << "No" << endl;
#define no cout << "no" << endl;

int asc(const void *a, const void *b) {
    return *(int *)a - *(int *)b;
}

int desc(const void *a, const void *b) {
    return *(int *)b - *(int *)a;
}

int main()
{
    int n;
    cin >> n;
    if (n <= 9) {
        cout << n << endl;
    }else if(n <= 99){
        cout << 9 << endl;
    }else if (n <= 999){
        cout << 9 + n - 99 << endl;
    }else if (n <= 9999){
        cout << 909 << endl;
    }else if (n <= 99999){
        cout << 909 + n - 9999 << endl;
    }else{
        cout << 90909 << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T,class U> using P = pair<T,U>;
template<class T> using vec = vector<T>;
template<class T> using vvec = vector<vec<T>>;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)

const ll M = 1e9 + 7;

vector<ll> fac(300001); //n!(mod M)
vector<ll> ifac(300001); //k!^{M-2} (mod M)
//a,bの範囲的にこれだけ配列を用意していけば十分

ll mpow(ll x, ll n){ //x^n(mod M) ←普通にpow(x,n)では溢れてしまうため，随時mod計算
    ll ans = 1;
    while(n != 0){
        if(n&1) ans = ans*x % M;
        x = x*x % M;
        n = n >> 1;
    }
    return ans;
}

ll comb(ll a, ll b){ //aCbをmod計算
    if(a == 0 && b == 0)return 1;
    if(a < b || a < 0)return 0;
    ll tmp = ifac[a-b]* ifac[b] % M;
    return tmp * fac[a] % M;
}

int main(){
    int n, k;
    cin >> n >> k;
    fac[0] = 1;
    ifac[0] = 1;
    for(ll i = 0; i<300000; i++){
        fac[i+1] = fac[i]*(i+1) % M; // n!(mod M)
        ifac[i+1] = ifac[i]*mpow(i+1, M-2) % M; // k!^{M-2} (mod M) ←累乗にmpowを採用
    }
    for(int i=1; i<=k; i++) {
        ll ans;
        if (i>1) ans = (comb(n-k+1, i)%M) * (comb(k-1, i-1)%M);
        else ans = comb(n-k+1, 1)%M; 
        cout << ans%M << endl;
    }
}

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

#define N 105

int main(){
    int n;
    cin >> n;
    int AdjMat[N][N];
    
    for (int i = 1; i <= n; i++ ){
        for (int j = 1; j <= n; j++){
            AdjMat[i][j] = 0;
        }
    }
    
    for (int i = 1; i <= n; i++){
        int u, k, v;
        cin >> u >> k;
        if ( k == 0 ) continue;
        for (int j = 1; j <= k; j++){
            cin >> v;
            AdjMat[u][v] = 1;
        }
        
    }
    
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            if ( j != n ) cout << AdjMat[i][j] << " ";
            else cout << AdjMat[i][j] << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3120
fun main(args: Array<String>) {
    agc021a()
}

fun agc021a() {
    val n = readLine()!!

    if (n.length == 1) return println(n)

    val answer =
        when {
            n.all { it == '9' } -> n.length * 9
            n.drop(1).all { it == '9' } -> n.sumBy { it.toString().toInt() }
            else -> n.first().toString().toInt() + (n.length - 1) * 9 - 1
        }

    println(answer)
}


Measured memory_bytes: 33852
#if __has_include("debug.h")
    #include "debug.h"
#else  
#include <bits/stdc++.h>
using namespace std;
#define d(...) 2;
#endif

#define int long long int
#define ld long double

#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl "\n"      

#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define ff first
#define ss second
#define eps 1e-10
#define PI acos(-1LL)

#define gcd(a,b)            __gcd((a),(b))
#define lcm(a,b)            ((a*b)/gcd(a,b))

void solve();

int32_t main()
{
    #ifdef DEBUG
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
    #endif 

    fast
    
    int t = 1;
	// cin>>t;
	
	while(t--)
	    solve();
	return 0;  
}

void solve()
{
	int i,j;
	int n;
	string s;
	cin>>n>>s;

	int cnt=0;

	for(i=0;i<=n-3;i++)
	{
		string tmp=s.substr(i,3);

		if(tmp=="ABC")
		{
			cnt++;
		}
	}
	cout<<cnt<<endl;

}

Measured memory_bytes: 3552
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> pll;
const ll mod=1e9+7;
//const ll mod=998244353;
const ll inf=5e18;

ll check(ll n) {
  map<ll,ll> cnt;
  for(ll i=2;i*i<=n;i++) {
    while(n%i==0) {
      cnt[i]++;
      n/=i;
    }
  }
  if(n!=1) cnt[n]++;
  for(auto p:cnt) {
    if(p.second%2) return 0;
  }
  return 1;
}

int main() {
  ll n,d;
  cin >> n >> d;
  mat x(n,vec(d));
  for(ll i=0;i<n;i++) for(ll j=0;j<d;j++) cin >> x[i][j];
  ll ans=0;
  for(ll i=0;i<n;i++) {
    for(ll j=i+1;j<n;j++) {
      ll tmp=0;
      for(ll k=0;k<d;k++) {
        tmp+=(x[i][k]-x[j][k])*(x[i][k]-x[j][k]);
      }
      if(check(tmp)) ans++;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define vd(T) vector<vector<T>>
#define v(T) vector<T>
#define mod (ll)(1e9+7)
#define pp(T) pair<T,T>
#define pb push_back
#define mp make_pair
#define NN 100005
#define IO ios_base::sync_with_stdio(NULL),cin.tie(0),cout.tie(0)
#define loop(i,a,b) for(ll i=a;i<b;i++)
#define DEBUG cout<<"***********DEBUGGING***********"<<endl
#include <ext/pb_ds/assoc_container.hpp> // Common file 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; 
ll power(ll a,ll b){ if(b==0) return 1; ll s=power(a,b/2); s*=s;if(b&1) return s*a; return s;}
ll powermod(ll a,ll b,ll m){ if(b==0) return 1; ll s=power(a,b/2);s*=s; s%=m; if(b&1) return (s*a)%m; return s;}
inline int add(ll a,ll b,ll m=0){
    if(m==0) return a+b;
    return (a%m+b%m)%m;
}

inline int sub(ll a,ll b ,ll m=0){
    if(m==0) return a-b;
    return ((a%m-b%m)%m+m)%m;
}

inline int mul(ll a,ll b,ll m=0){
    if(m==0)return (a*b);
    return ((a%m)*(b%m))%m;
}

inline int div(ll a,ll b,ll m=0){
    if(m==0) return a/b;
    return ((a%m)*(powermod(a,b,m-2)%m))%m;
}

bool isopen(char c){
    return ((c=='(')||(c=='{')||(c=='['));
}

ll longest_balanced_parenthesis(string a,ll n){
    stack<char> s;
    ll start=0;
    ll ans=0,m=0;
    for(ll i=0;i<n;i++){
        if(isopen(a[i])){
            s.push(a[i]);
        }
        else{
            if(isopen(a[i])|| s.empty()){
                m=max(m,ans);
                continue;
            }
            else{
                s.pop();
                ans+=2;
                m=max(ans,m);
            }
        }
    }

    return m;

}

ll setup_k(ll *a,ll k){
  ordered_set x;
  // Now , insert and then check number of integers less than k by just using x.order_of_key(k+1)
}

int main() {

    IO; 

    ll n,k;
    cin>>n>>k;
    ll cnt=0;
    ll n1=ceil(log(k))+1;
    if((k&(k-1))==0){
        n1=log(k);
    }
    long double ans=0;
    for(ll i=1;i<=n;i++){
        // i*2^x >=k
        if(i>=k){
            ans+=1;
            continue;
        }
        double y=ceil(log2(k/(1.0*i)));
        ans+=(1.0)/power(2,y);
    }
    ans=(ans*1.0)/n;
    cout<<fixed<<setprecision(10)<<ans<<endl;
    

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define debug(x) cout << #x << ": " << (x) << endl
using namespace std;

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

using Int = int;
using Double = double;

using P = pair<Int, Int>;
using V = vector<Int>;
using M = vector<V>;

const double PI  = 3.141592653589793238463;
const int MOD = 1000000007;
const Int INF = numeric_limits<Int>::max() / 3;

template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
    for(T& x: vec){
        is >> x;
    }
    return is;
}

template<typename T>
string join(const vector<T>& vec, string sep = " "){
    stringstream ss;
    for(int i = 0; i < vec.size(); i++){
        ss << vec[i] << (i + 1 == vec.size() ? "" : sep);
    }
    return ss.str();
}

char solve(char x, char y){
    if(x < y){
        return '<';
    }else if(x > y){
        return '>';
    }else{
        return '=';
    }
}

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

    char x, y;
    cin >> x >> y;
    cout << solve(x, y) << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define che
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define PB push_back
#define MP make_pair
using namespace std;
typedef long long LL;
const LL xx[10] = {1019,1021,1031,1033,1039,1049,1051,1061,1063,1069};
int main(){
	LL x, y;
	scanf("%lld%lld", &x, &y);
	if ( x%y==0) printf("-1\n");
		else{
			for (int i=0; i<10; i++)
				if ( y%xx[i]){
					printf("%lld\n", x*xx[i]);
					break;
				}
		}
	
	return 0;
}


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

int main(){
    int n,m,a;
    cin >> n >> m;
    vector<int> dp(n+1);
    vector<bool> h(n+1,true);
    for(int i=0;i<m;i++){
        cin >> a;
        h.at(a)=false;
    }
    dp.at(0)=1;dp.at(1)=h.at(1);
    for(int i=2;i<=n;i++){
        dp.at(i)=(dp.at(i-2)*h.at(i-2)+dp.at(i-1)*h.at(i-1))%1000000007;
    }
    cout << dp.at(n) << endl;
    return 0;
}

Measured memory_bytes: 3748
#include<iostream>
#include<vector>
#include<string>
#include<sstream>
int main()
{
	std::vector<std::string::size_type>apple, peach;
	std::string str;
	std::getline(std::cin, str);
	while (true)
	{
		static int index = -1;
		index = str.find("apple", index + 1);
		if (index == std::string::npos)
		{
			break;
		}
		apple.push_back(index);
	}
	while (true)
	{
		static int index = -1;
		index = str.find("peach", index + 1);
		if (index == std::string::npos)
		{
			break;
		}
		peach.push_back(index);
	}
	for (auto i : apple)
	{
		str.replace(i, 5, "peach");
	}
	for (auto i : peach)
	{
		str.replace(i, 5, "apple");
	}
	std::cout << str << std::endl;
	return 0;
}


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

using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ll;
typedef long int li;

int main()
{
    IOS;
    //freopen("fr.txt","r",stdin);
    int m,n;
    cin>>m>>n;
    int a=min(m,n);
    int b=max(m,n);
    for(int i=1;i<=b;i++){
        cout<<a;
    }
    cout<<endl;
    return 0;
}

Measured memory_bytes: 3636
//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")
   
//#include <x86intrin.h>
#include <bits/stdc++.h>   
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace __gnu_pbds;
using namespace std;

template<typename T> using ordered_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
     
#define F first
#define S second           
#define lb lower_bound               
#define ub upper_bound
#define pb push_back
#define pf push_front    
#define ppb pop_back
#define mp make_pair
#define bpp __builtin_popcountll                                                                                        
#define sqr(x) ((x) * (x)) 
#define al 0x3F3F3F3F
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define in insert
#define ppf pop_front
#define endl '\n'
#define int long long
 
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
 
const int mod = (int)1e9 + 7;
const int N = (int)3e5 + 123;
const ll inf = (ll)1e18 + 1;

const double pi = acos (-1.0);
const double eps = 1e-7;                  
const int dx[] = {0, 0, 1, 0, -1};
const int dy[] = {0, 1, 0, -1, 0};

int n, k, pref[N], ans, a[N];
map <int, int> cnt;

inline void boost () {                    
   ios_base :: sync_with_stdio (NULL);
   cin.tie (NULL), cout.tie (NULL);          
}                                                     

inline void Solve () {
   cin >> n >> k;
   for (int i = 1; i <= n; i ++) {
      int x;
      cin >> x;
      pref[i] = pref[i - 1] + x;
      a[i] = pref[i] - i;
      if (a[i] < 0) a[i] += k;
   }
   cnt[0] ++;
   for (int i = 1; i <= n; i ++) {
      if (i >= k) cnt[a[i - k] % k] --;
      ans += cnt[a[i] % k];
      cnt[a[i] % k] ++;
   }
   cout << ans;
}

main () {                                       
// freopen (".in", "r", stdin);    
// freopen (".out", "w", stdout);              
   boost ();
   int tt = 1;
   //cin >> tt;   
   while (tt --) {
      Solve ();
   }                                               
   return 0;      
}
                          

Measured memory_bytes: 16384
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int main() {
    ll n; cin>>n;
    vector<ll> a;
    
    ll m = n;
    
    for(ll i=2;i*i<=n; ++i){
        while(m%i==0){
            if(m%i==0){
                a.push_back(i);
                m/=i;
            }
            else break;
        }
    }
    if(m!=1)a.push_back(m);
    
    int n2 = a.size();
    ll ans = 0;
    
    int cc = 1;
    rep(i, n2){
        if(a[i]==a[i+1])++cc;
        else{
            int res = 1;
            while(cc>0){
                if(cc>=res){
                    ++ans;
                    cc-=res;
                    ++res;
                }
                else break;
            }
            cc=1;
        }
    }
    cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3612
#include<iostream>
using namespace std;
typedef long int li;
#define rep(i,n) for(int i=0;i<(n);i++)
#define df 0
#define Please return
#define AC 0

int main(){
  li n,k; cin >>n >>k;
  li ans=1;
  rep(i,n){
    if(i==0) ans*=k;
    else ans*=k-1;
  }
  cout << ans << "\n";
  Please AC;
}


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

using namespace std;
typedef long long ll;

int main(){
    string s;
    getline(cin, s);
    ll n0 = (s.at(0) == '1');
    ll n1 = (s.at(0) == '0');
    for(int i = 1; i < s.size(); ++i){
        ll new_n0 = (s.at(i) == '1') + n1;
        ll new_n1 = (s.at(i) == '0') + n0;
        n0 = new_n0;
        n1 = new_n1;
    }
    cout << min(n0, n1) << endl;
    return 0;
}


Measured memory_bytes: 512
import java.util.Arrays;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] x = new int[n];
		for(int i = 0; i < n; i++) {
			x[i] = sc.nextInt();
		}
		int[] y = x.clone();
		Arrays.sort(y);

		int mid1 = y[y.length/2-1];
		int mid2 = y[y.length/2];
		for(int i = 0; i < n; i++) {
			if(x[i] <= mid1)
				System.out.println(mid2);
			else
				System.out.println(mid1);
		}
	}
}


Measured memory_bytes: 90852
s = input()
index=0
valL=[]
countL=[]
index=0
while index < len(s):
    if s[index] in valL:
        targetI = valL.index(s[index])
        countL[targetI]+=1
    else:
        valL.append(s[index])
        countL.append(1)
    index+=1
if len(valL) == 2:
    if countL[0]==2 and countL[1]==2:
        print("Yes")
    else:
        print("No")
else:
    print("No")

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

using namespace std;

int main(){
  int n;
  cin >> n;
  vector<int> d(n);
  for(int i=0;i<n;i++){
    cin >> d[i];
  }
  sort(d.begin(),d.end());
  if(d[n/2-1]==d[n/2]){
    cout << 0 << endl;
  }
  else{
    cout << d[n/2]-d[n/2-1] << endl;
  }
}


Measured memory_bytes: 768
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 105;

int main() {
   // freopen("in.cpp","r",stdin);
    string s;
    cin>>s;
    int cnt=0;
    for(int i=s.size()-2;i>=0;i--)
    if(s[i]!=s[i+1])cnt++;
    cout<<cnt<<endl;
    return 0;
}


Measured memory_bytes: 512
#include <iostream>
using namespace std;
int main(void){
    long long int A, B;
    cin >> A >> B;
    
    long long int x = A * B;
    if (A < B) {
        int tmp = A;
        A = B;
        B = tmp;
    }
    int r = A % B;
    while (r != 0) {
        A = B;
        B = r;
        r = A % B;
    }
    cout << x/B << endl;
}

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

int main() {
  int n;
  int a;
  
  cin >> n >> a;
  
  if( (n % 500) <= a)
  {
    cout << "Yes" <<endl;
  }
  else
  {
    cout << "No" <<endl;
  }
}

Measured memory_bytes: 256
//   _/                _/                 _/_/_/   _/
//_/_/_/_/   _/_/   _/_/_/_/   _/_/    _/       _/_/
// _/     _/    _/   _/     _/    _/  _/_/_/     _/
//_/     _/    _/   _/     _/    _/  _/    _/   _/
// _/_/   _/_/       _/_/   _/_/      _/_/     _/
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const double pi=3.14159265358979323846;
const int inf=1e9;
const ll INF=1e18;
typedef pair<int,int> P;
int main() {
  cin.tie(0),cout.tie(0);
  ios::sync_with_stdio(false);
  int a;
  string s;
  cin >> a >> s;
  if(a>=3200) {
    cout << s << endl;
  }
  else {
    cout << "red" << endl;
  }
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define endl '\n'
#define mod 1000000007

using namespace std;

int main()
{
    string s;
    cin>>s;
    for(int i=0;i<s.size();i++)
    {
        if(i+1<s.size() && s[i]==s[i+1])return cout<<i+1<<' '<<i+2 ,0;
        if(i+2<s.size() && s[i+2]==s[i])return cout<<i+1<<' ' <<i+3 , 0;
    }
    cout<< -1<< ' '<<-1;
    return 0;
}
/*int n;
    cin>>n;
    ll arr[n], ans=1e18;
    ll sum1 = 0 , sum2 = 0;

    for(int i=0;i<n;i++)
        cin>>arr[i];


    for(int b=-10;b<=10;b++)
    {
        ll cnt=0;
        ll sum1=0, sum2=0;
        for(int i=0;i<n;i++)
            cnt+=abs(arr[i]-(b+i)),
            sum1+=arr[i],
            sum2+=b+i;
        cout<<b<<' ' <<cnt<<' '<<sum1-sum2<<' '<<sum1<<' '<<sum2<<endl;
    }*/


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

int main(void){
  int n,ans,mn;
  
  cin >> n;
  mn=n+1; ans=0;
  for (int i=0; i<n; i++){
    int a; cin >> a;
    if (a<mn){
      mn = a;
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define int long long
signed main(){
    string s;
    cin>>s;
    string ans;
    for(int i=0;i<s.size();i++) {
        if(s[i]=='0')ans+="0";
        else if(s[i]=='1')ans+="1";
        else {
            if(ans.size()!=0)ans.erase(ans.size()-1,1);
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for(ll i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i,n) for(ll i = n;i >= 0;--i)
#define FOR(i,m,n) for(ll i = m, i##_len=(n);i <i##_len; ++i)
#define all(x) (x).begin(),(x).end()
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; }
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
const int INF = 1e9;
const ll LLINF = 1e16;

int main(void){
    int S, W;
    cin >> S >> W;

    if(S <= W){
        cout << "unsafe" << endl;
    }
    else{
        cout << "safe" <<endl;
    }

    
    return 0;
}


Measured memory_bytes: 3596
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.IOException;
import java.io.InputStream;

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

    static class BIMissYou {
        PrintWriter out;
        InputReader in;

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            this.out = out;
            this.in = in;
            String st = n();
            StringBuilder str = new StringBuilder();
            for (int i = 0; i < st.length(); i++)
                str.append('x');
            pn(str);
        }

        String n() {
            return in.next();
        }

        void pn(Object o) {
            out.println(o);
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1)
                throw new UnknownError();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new UnknownError();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public String next() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuffer res = new StringBuffer();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));

            return res.toString();
        }

        private boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

    }
}



Measured memory_bytes: 23380
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define tc() ll T;cin>>T;while(T--)
#define pb push_back

struct cmp {
    bool operator() (const pair<ll,ll> &a,const pair<ll,ll> &b){
        return a.first>b.first;
    }
};

int main() {
    
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    
    /*-----------------Code Begins Here------------------*/
    
    ll n; cin>>n;
    char s[n];
    ll cr=0,cr1=0;
    for(ll i=0;i<n;i++){
        cin>>s[i];
        if(s[i] == 'R') cr++;
    }
    for(ll i=0;i<cr;i++){
        if(s[i] == 'R') cr1++;
    }
    cout<<cr-cr1;
    
    /*------------------Code Ends Here-------------------*/
    
    return 0;
}

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



int main(void)
{
    int x;
    cin >> x;

    int ans = 0;
    ans += (x / 500)*1000;
    x %= 500;
    ans += (x/5)*5;
    cout << ans << endl;

    return 0;
}

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

using namespace std;
typedef long long ll;
typedef pair<ll, ll> p_ll;

template<class T>
void debug(T itr1, T itr2) { auto now = itr1; while(now<itr2) { cout << *now << " "; now++; } cout << endl; }
#define repr(i,from,to) for (int i=(int)from; i<(int)to; i++)
#define all(vec) vec.begin(), vec.end()
#define rep(i,N) repr(i,0,N)
#define per(i,N) for (int i=(int)N-1; i>=0; i--)

const ll MOD = pow(10,9)+7;
const ll LLINF = pow(2,61)-1;
const int INF = pow(2,30)-1;

vector<ll> fac;
void c_fac(int x=pow(10,6)+10) { fac.resize(x,true); rep(i,x) fac[i] = i ? (fac[i-1]*i)%MOD : 1; }
ll inv(ll a, ll m=MOD) { ll b = m, x = 1, y = 0; while (b!=0) { int d = a/b; a -= b*d; swap(a,b); x -= y*d; swap(x,y); } return (x+m)%m; }
ll nck(ll n, ll k) { return fac[n]*inv(fac[k]*fac[n-k]%MOD)%MOD; }
ll gcd(ll a, ll b) { if (a<b) swap(a,b); return b==0 ? a : gcd(b, a%b); }
ll lcm(ll a, ll b) { return a/gcd(a,b)*b; }

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

struct edge { ll to; ll d; };
vector<vector<edge>> adj;

vector<ll> dijkstra(int n=0) {
  int N = adj.size();
  auto c = [](const p_ll &x, const p_ll &y){return x.second>y.second;};
  priority_queue<p_ll, vector<p_ll>, decltype(c)> q(c);
  vector<ll> result(N,LLINF); result[n] = 0; q.push(make_pair(n,0));
  while(q.size()) {
    p_ll now = q.top(); q.pop();
    ll np = now.first, nd = now.second;
    if (nd>result[np]) continue;
    for (auto x: adj[np]) {
      if (result[x.to]<=result[np]+x.d) continue;
      q.push(make_pair(x.to, result[np]+x.d));
      result[x.to] = result[np]+x.d;
    }
  }
  return result;
}

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

int main() {
  ll N, M, S; cin >> N >> M >> S;
  S = min(S,N*50);
  adj.resize(N*(N*50+1));
  rep(i,M) {
    ll U, V, A, B; cin >> U >> V >> A >> B;
    U--; V--;
    repr(j,A,N*50+1) {
      adj[U*(N*50+1)+j].push_back({V*(N*50+1)+(j-A),B});
      adj[V*(N*50+1)+j].push_back({U*(N*50+1)+(j-A),B});
    }
  }
  rep(i,N) {
    ll C, D; cin >> C >> D;
    repr(j,1,N*50+1) adj[i*(N*50+1)+j].push_back({i*(N*50+1)+(j-1),0});
    repr(j,C,N*50+1) adj[i*(N*50+1)+(j-C)].push_back({i*(N*50+1)+j,D});
  }
  vector<ll> d = dijkstra(S);
  repr(i,1,N) {
    ll result = d[i*(N*50+1)];
    cout << result << endl;
  }
  return 0;
}

Measured memory_bytes: 25884
#include<stdio.h>
int search(int);
int n;
int l[10000];
int main(){
  int i;
  int q;
  int q_n;
  int result=0;
  scanf("%d",&n);
  for(i=0;i<n;i++)scanf("%d",&l[i]);
  scanf("%d",&q);
  for(i=0;i<q;i++){
    scanf("%d",&q_n);
    result+=search(q_n);
  }
  printf("%d\n",result);
  return 0;
}
int search(int x){
  int i;
  int flag=0;
  for(i=0;i<n;i++)if(x==l[i]){
      flag=1;
      break;
    }
  return flag;
}



Measured memory_bytes: 2068
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = uint32_t;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

template<class T>
class BIT {
    vector<T> bit;
public:
    BIT(int n): bit(vector<T>(n+1, 0)){}

    T sum(int k){
        T ret = 0;
        for (++k; k > 0; k -= (k & -k)) ret += bit[k];
        return ret;
    }

    void add(int k, T x){
        for (++k; k < bit.size(); k  += (k & -k)) bit[k] += x;
    }
};
int main() {
    int n, q;
    cin >> n >> q;
    BIT<int> S(n+1);
    for (int i = 0; i < q; ++i) {
        int c;
        scanf("%d", &c);
        if(c == 0){
            int s, t, x;
            scanf("%d %d %d", &s, &t, &x);
            S.add(s-1, x);
            S.add(t, -x);
        }else {
            int x;
            scanf("%d", &x);
            printf("%d\n", S.sum(x-1));
        }
    }
    return 0;
}


Measured memory_bytes: 3392
// Package main provides
//
// File:  c.go
// Author: ymiyamoto
//
// Created on Fri Dec 21 09:33:56 2018
//
package main

import (
	"fmt"
)

func abs(a int) int {
	if a < 0 {
		return -a
	}

	return a
}

func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

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

func main() {
	var N, X int
	fmt.Scan(&N, &X)

	arr := make([]int, N)
	for i := range arr {
		fmt.Scan(&arr[i])
		arr[i] -= X
		arr[i] = abs(arr[i])
	}

	ans := arr[0]
	for _, a := range arr {
		ans = gcd(ans, a)
	}
	fmt.Println(ans)
}


Measured memory_bytes: 5504
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define COUT(x) cout<<(x)<<endl
#define dump(x)  cout << #x << " = " << (x) << endl;
using ll = long long;
using P = pair<int,int>;
using Graph = vector<vector<int>>;
using M = map<int,int>;
using PQ = priority_queue<int>;
using PQG = priority_queue<int, vector<int>, greater<int>>;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

int main() {
  ll x; cin >> x;
  ll n = 100;
  ll i = 1;
  while(1) {
    n*=1.01;
    if (n >= x) break;
    i++;
  }
  COUT(i);
  return 0;
}


Measured memory_bytes: 3632
#include <iostream>
#include <array>
#include <string>

const int NIL = -1;
struct node
{
  int parent = NIL;
  int left = NIL;
  int right = NIL;
};

using binaryTree =  std::array<node, 25>;

std::string getType(node n)
{
  if (n.parent == NIL) return "root";
  else if (n.left == NIL && n.right == NIL)
    return "leaf";
  else
    return "internal node";
}


int getRootID(binaryTree tree, int n)
{
  for (int i=0; i<n; ++i)
    {
      if (getType(tree[i]) == "root")
        {
          return i;
        }
    }
  return NIL;
}

auto print = [](auto x){std::cout << " " << x;};

void preOrder(binaryTree tree, int root_id)
{
  print(root_id);
  if (tree[root_id].left != NIL)
    preOrder(tree, tree[root_id].left);
  if (tree[root_id].right != NIL)
    preOrder(tree, tree[root_id].right);
}

void inOrder(binaryTree tree, int root_id)
{
  if (tree[root_id].left != NIL)
    inOrder(tree, tree[root_id].left);
  print(root_id);
  if (tree[root_id].right != NIL)
    inOrder(tree, tree[root_id].right);
}

void postOrder(binaryTree tree, int root_id)
{
  if (tree[root_id].left != NIL)
    postOrder(tree, tree[root_id].left);
  if (tree[root_id].right != NIL)
    postOrder(tree, tree[root_id].right);
  print(root_id);
}


int main ()
{
  int n;
  std::cin >> n;

  binaryTree tree;
  for (int i=0; i<n; ++i)
    {
      int id, left, right;
      std::cin >> id >> left >> right;
      tree[id].left = left;
      tree[id].right = right;
      tree[left].parent = id;
      tree[right].parent = id;
    }

  auto root_id = getRootID(tree, n);

  std::cout << "Preorder\n";
  preOrder(tree, root_id);
  std::cout << std::endl;

  std::cout << "Inorder\n";
  inOrder(tree, root_id);
  std::cout << std::endl;

  std::cout << "Postorder\n";
  postOrder(tree, root_id);
  std::cout << std::endl;


}



Measured memory_bytes: 3216
# -*- coding: utf-8 -*-


def main():
    import sys
    input = sys.stdin.readline

    n, k = map(int, input().split())
    count = [[] for _ in range(n)]

    for i in range(k):
        di = int(input())
        a = list(map(int, input().split()))

        for ai in a:
            count[ai - 1].append(i)

    ans = 0

    for c in count:
        if len(c) == 0:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 9188
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    ans=INF
    for i in range(1,int(n**.5)+1):
        if n%i: continue
        ans=min(ans,max(len(str(i)),len(str(n//i))))
    print(ans)
resolve()

Measured memory_bytes: 39664
n = int(input())
a = list(map(int,input().split()))
a.sort(reverse=True)

tmp = a[0]
ans = []
cnt = 0
for i in range(1,len(a)):
    if tmp == a[i]:
        cnt += 1
        if cnt == 1 or cnt == 3:
            ans.append(tmp)
    else:
        tmp = a[i]
        cnt = 0


if len(ans) < 2:
    print(0)
else:
    print(ans[0]*ans[1])

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

int	main() {
	int H, W;
	cin >>H >>W;
	vector<vector<int>> A(H+2, vector<int> (W+2, 0));
	vector<vector<int>> Q(0);
	for (int i=1; i<=H; i++)
		for (int j=1; j<=W; j++) {
			char C;
			cin >>C;
			if ('#'==C) {
				A.at(i).at(j)=1;
				Q.push_back({i, j});
			}
		}
	for (int i=0; i<=H+1; i++) {
		A.at(i).at(0)=-1;
		A.at(i).at(W+1)=-1;
	}
	for (int i=0; i<=W+1; i++) {
		A.at(0).at(i)=-1;
		A.at(H+1).at(i)=-1;
	}
	int S=1;
	while(true) {
		vector<vector<int>> QQ(0);
		for (int k=0; k<Q.size(); k++) {
			int i=Q.at(k).at(0);
			int j=Q.at(k).at(1);
			if (0==A.at(i-1).at(j)) {
				A.at(i-1).at(j)=S+1;
				QQ.push_back({i-1, j});
			}
			if (0==A.at(i+1).at(j)) {
				A.at(i+1).at(j)=S+1;
				QQ.push_back({i+1, j});
			}
			if (0==A.at(i).at(j-1)) {
				A.at(i).at(j-1)=S+1;
				QQ.push_back({i, j-1});
			}
			if (0==A.at(i).at(j+1)) {
				A.at(i).at(j+1)=S+1;
				QQ.push_back({i, j+1});
			}
		}
		if (0==QQ.size())
			break;
		Q=QQ;
		S++;
	}
	S--;
	cout <<S <<endl;
	return 0;
}


Measured memory_bytes: 59944
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPR(i, n) for (int i = n - 1; i >= 0; --i)
#define FOR(i, m, n) for (int i = m; i < n; ++i)
#define FORR(i, m, n) for (int i = m; i >= n; --i)
#define ALL(v) (v).begin(),(v).end()
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const ll INF=1LL<<60;
const int inf=(1<<30)-1;
const int mod=1e9+7;
int dx[8]={1,0,-1,0,-1,-1,1,1};
int dy[8]={0,1,0,-1,-1,1,-1,1};
const int nmax=100005;
ll fac[nmax],finv[nmax],inv[nmax];
void COMinit(){
  fac[0]=fac[1]=1;
  finv[0]=finv[1]=1;
  inv[1]=1;
  for(int i=2;i<nmax;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 com(int n,int k){
  if(n<k||n<0||k<0){
    return 0;
  }
  return fac[n]*(finv[k]*finv[n-k]%mod)%mod;
}
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;cin >> n;
    COMinit();
    vector<int> a(n+1);
    vector<int> c(n,-1);
    int s,t;
    REP(i,n+1){
        cin >> a[i];
        if(c[a[i]-1]!=-1){
            s=c[a[i]-1],t=i;
        }
        else{
            c[a[i]-1]=i;
        }
    }
    FOR(i,1,n+2){
        cout << (com(n+1,i)-com(s+n-t,i-1)+mod)%mod << endl;
    }
}

Measured memory_bytes: 6308
[N,M]=[int(i)for i in input().split()]
#setの配列を持つ
edge=[set() for _ in range(N+1)]
#print(edge,shortestPath)
for i in range(M):
  [a,b]=[int(i)for i in input().split()]
  #print(a,b)
  edge[a].add(b)
  edge[b].add(a)
#print(edge)

shortestPath=[N+1]*(N+1)
shortestPath[1]=0
nextEdgeKouho=set([1])
#1番目の部屋から最短距離を更新して行く
while(len(nextEdgeKouho)>0):
  nextNextEdgeKouho = set([])
  for start in nextEdgeKouho:
    tmpshortestpath=shortestPath[start]
    for end in edge[start]:
      if shortestPath[end] == N+1:
        shortestPath[end] = start
        nextNextEdgeKouho.add(end)
  #print(nextNextEdgeKouho)
  nextEdgeKouho=nextNextEdgeKouho
#print()
#print(shortestPath[2:])
if N + 1 in shortestPath[1:]:
  print("No")
else:
  print("Yes")
  [print(i) for i in shortestPath[2:]]

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

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
using std::bitset;

#define rep(i,n)    for(int i=0; i<(int)(n); i++)
#define reps(i,s,e) for(int i=s; i<(int)(e); i++)
#define coutd(i) cout << std::fixed << std::setprecision(i)
typedef long double ld;
typedef long long ll;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef std::pair<int, int> pii;
typedef std::pair<ll, ll> pll;

template<class T>
using Set = std::set<T>;
template<class T, class U>
using Map = std::map<T, U>;

template<class T>
using Graph = vector<vector<T>>;

const int INT_BIG = 1<<28;

int main() {
    string s;
    cin >> s;
    int len = s.length();
    int count = 0;
    rep(i, len) {
        count += (int)(s[i] - '0');
        count %= 9;
    }
    cout << (count == 0 ? "Yes" : "No") << endl;
}

Measured memory_bytes: 3732
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
ll dp[100005];
ll a[201];
int main(){
    ll n, k,i,j;
    scanf("%lld %lld",&n, &k);
    dp[0] = 0;
    for(i = 0; i < n; i++) {cin>>a[i];
  dp[a[i]] = 1;}
    for(i = a[0]+1; i <= k; i++){
        dp[i] = 1;
        for(j = 0; j <n && a[j] <= i; j++){
            dp[i] &= dp[i-a[j]] ;
        }
        dp[i] = 1-dp[i];
    }
    if(dp[k])
      cout<<"First";
    else cout<<"Second";
    return 0;
}





Measured memory_bytes: 1024
# 5, 19, 0
n, m = gets.split.map &:to_i # N個おける, M個地点
x = gets.split.map &:to_i
x.sort! # logM

a = []
(x.size - 1).times do |i| # M
  a << x[i + 1] - x[i]
end
a.sort!
(n - 1).times do # N
  # break if a.size < 2
  # ind = a.index(a.max) # M
  # a[ind] = 0
  a.pop
end

if a.empty?
  p 0
  exit
end
p a.inject(&:+) # N
# a.index(a.max)


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

int main(){
    int M,D;
    cin >> M >> D;
    int cnt = 0;
    for(int i=1;i<=M;i++){
        for(int d=1;d<=D;d++){
            int d10 = d/10;
            int d1 = d%10;
            if(d10>1 && d1 >1){
                if(i==(d10*d1)){
                    // cout << i << ":" << d10 << " " << d1 << endl;
                    cnt++;
                }
            }
        }
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include <boost/multiprecision/cpp_ll.hpp>
//typedef boost::multiprecision::cpp_ll ll;
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
ll inf=(ll)1E18;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
#define endl "\n"
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);



int main(){fastio
    ll n,k;cin>>n>>k;
    ll a[n];rep(i,0,n-1)cin>>a[i];
    ll l=0;
    ll r=powl(10,9)+1;
    while(r-l>1){
        ll mid=(r+l)/2;
        ll sum=0;
        rep(i,0,n-1){
            ll l=(a[i]+mid-1)/mid-1;
            sum+=l;
        }
        if(sum>k){
            l=mid;
        }else{
            r=mid;
        }
    }
    cout<<r<<endl;
    
}



Measured memory_bytes: 5168
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = uint32_t;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

using real = double;
real EPS = 1e-10;
struct Point3 {
    real x, y, z;
    Point3& operator+=(const Point3 a) { x += a.x; y += a.y; z += a.z;  return *this; }
    Point3& operator-=(const Point3 a) { x -= a.x; y -= a.y; z -= a.z; return *this; }
    Point3 operator+(const Point3 a) const {return Point3(*this) += a; }
    Point3 operator-(const Point3 a) const {return Point3(*this) -= a; }
    explicit Point3(real a = 0, real b = 0, real c = 0) : x(a), y(b), z(c) {};
};


inline real dot(Point3 a, Point3 b){ return a.x*b.x + a.y*b.y + a.z*b.z; }
inline Point3 cross(Point3 a, Point3 b){
    return Point3(a.y*b.z-a.z*b.y, a.z*b.x-a.x*b.z, a.x*b.y-a.y*b.x);
}
inline real abs(Point3 a){ return sqrt(dot(a, a)); }

struct Segment {
    Point3 a, b;
    Segment(Point3 x, Point3 y) : a(x), b(y) {};
};


double distance(Segment l, Point3 c){
    if(dot(l.b-l.a, c-l.a) <= 0) return abs(c-l.a);
    if(dot(l.a-l.b, c-l.b) <= 0) return abs(c-l.b);
    return abs(cross(l.b-l.a, c-l.a)) / abs(l.a-l.b);
}

struct Sphere{
    Point3 c;
    double r;
    Sphere(){};
    Sphere(Point3 c, double r): c(c), r(r){};
};

bool intersect(Segment s,Sphere c){
    double d=distance(s,c.c);
    return d < c.r+EPS;
}

int main() {
    int n, q;
    cin >> n >> q;
    vector<Sphere> v(n);
    vector<ll> x(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i].c.x >> v[i].c.y >> v[i].c.z >> v[i].r >> x[i];
    }
    for (int i = 0; i < q; ++i) {
        double a, b, c, d, e, f;
        cin >> a >> b >> c >> d >> e >> f;
        Segment S(Point3(a, b, c), Point3(d, e, f));
        uint64_t ans = 0;
        for (int j = 0; j < n; ++j) {
            if(intersect(S, v[j])) ans += x[j];
        }
        cout << ans << "\n";
    }
    return 0;
}


Measured memory_bytes: 3224