akhauriyash/Code-Regression huggingface dataset:
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
inf=1000000000
wf=[[inf]*(h*w) for i in range(h*w)]
for i in range(h*w):
    k,l=i//w,i%w
    #print(l)
    if s[k][l]=="#":
        continue
    if k!=0:
        if s[k-1][l]==".":
            wf[i][i-w]=1
    if k!=h-1:
        if s[k+1][l]==".":
            wf[i][i+w]=1
    if l!=0:
        if s[k][l-1]==".":
            wf[i][i-1]=1
    if l!=w-1:
        if s[k][l+1]==".":
            wf[i][i+1]=1
    wf[i][i]=0
for i in range(h*w):
    for j in range(h*w):
        for k in range(h*w):
            wf[j][k]=min(wf[j][k],wf[j][i]+wf[i][k])
ans=0
for i in range(h*w):
    for j in range(h*w):
        if wf[i][j]!=inf:
            ans=max(ans,wf[i][j])
print(ans)
#print(wf)

Measured memory_bytes: 44280
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ll, P> P3;
typedef pair<P ,P> PP;
constexpr ll MOD = ll(1e9) + 7;
constexpr int IINF = INT_MAX;
constexpr ll LLINF = LLONG_MAX;
constexpr int MAX_N = int(2e5) + 5;
constexpr double EPS = 1e-8;
constexpr int di[] = {0, 1, 0, -1}, dj[] = {1, 0, -1, 0};
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define SORT(v) sort((v).begin(), (v).end())
#define SORTR(v) sort((v).rbegin(), (v).rend())
#define ALL(v) (v).begin(), (v).end()

int n, k, c[5005], r[5005], dmin[5005][5005], ans;
vector<vector<int> > g;

int main() {
    cin >> n >> k;
    for(int i=0;i<n;i++){
        cin >> c[i] >> r[i];
    }
    g.resize(n);
    for(int i=0;i<k;i++){
        int a, b;
        cin >> a >> b;
        a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for(int i=0;i<n;i++){
        g[i].push_back(i);
        fill(dmin[i], dmin[i]+n+1, IINF);
    }
    priority_queue<P3,vector<P3>,greater<P3> > que;
    dmin[0][0] = 0;
    que.push({dmin[0][0],{0,0}});
    while(!que.empty()){
        P3 p = que.top();
        que.pop();
        int now = p.second.first, rs = p.second.second;
        if(now == n-1){
            ans = p.first;
            break;
        }
        if(dmin[now][rs] < p.first)continue;
        if(rs > 0){
            for(auto to : g[now]){
                if(dmin[to][rs-1] > dmin[now][rs]){
                    dmin[to][rs-1] = dmin[now][rs];
                    que.push({dmin[to][rs-1], {to, rs-1}});
                }
            }
        }
        else{
            if(dmin[now][r[now]] > dmin[now][0] + c[now]){
                dmin[now][r[now]] = dmin[now][0] + c[now];
                que.push({dmin[now][r[now]],{now, r[now]}});
            }
        }
    }
    cout << ans << endl;
    return 0;
}



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

int main() {
  
  int N=0, A=0, B=0;
  
  cin >> N;
  
  if(N==1) {
    
    cout << "Hello World" << endl;
    
  } else if(N==2) {
    
    cin >> A;
    cin >> B;
    
    int sum = A+B;
    
    cout << sum << endl;
    
  }
  
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstdint>
#include <algorithm>
#include <cmath>
#include <vector>
#include <unordered_map>


int main()
{
	uint64_t A, B;

	std::cin >> A >> B;

	uint64_t C;

	if (A == 1 || B == 1)
	{
		std::cout << 1 << std::endl;
	}
	else if (A * B % 2 == 0)
	{
		std::cout << A * B / 2 << std::endl;
	}
	else
	{
		std::cout << A * B / 2 + 1 << std::endl;
	}

	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
	char st[27];
	while(~scanf("%s", st))
	{
		int a[27]={0},i=-1, flag = 0;
		while(st[++i] != 0)
		{
			if(a[st[i]-97])
			{
				flag=1;
				break;
			}
			else a[st[i]-97]++;
		}
		if(flag)
			printf("no\n");
		else
			printf("yes\n");
	}
	return 0;
}

Measured memory_bytes: 256
n,m,k = map(int,input().split())
mod = 998244353

fact = [1,1]
finv = [1,1]
inv = [0,1]

for i in range(2,n+5):
    fact.append((fact[-1]*i)%mod)
    inv.append((inv[mod%i]*(mod-mod//i))%mod)
    finv.append((finv[-1]*inv[-1])%mod)

def nCr(n,r,mod):
    if r > n:
        return 0
    else: 
        return fact[n]*finv[r]*finv[n-r]%mod

x = m%mod

a = pow(m-1,n-1,mod)
x = (a*x)%mod

ans = x%mod
for i in range(1,k+1):
    x = m*pow(m-1,n-1-i,mod)
    a = nCr(n-1,i,mod)
    ans += (a*x)%mod
    ans %= mod
print(ans)


Measured memory_bytes: 32816
s = input()

a = [s[0]]
i = 1
while i<len(s):
    if s[i]!=a[-1]:
        a.append(s[i])
        i+=1
    else:
        if i==len(s)-1:
            break
        else:
            a.append(s[i:i+2])
            i+=2
print(len(a))


Measured memory_bytes: 53728
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N, M = getlist()
	D = defaultdict(lambda:1)
	A = []
	for i in range(N):
		a = list(reversed(getlist()))
		A.append(a)

	if M == 1:
		print(N)
		return

	ans = INF
	for i in range(M - 1):
		cnt = [0] * M
		for j in range(N):
			cnt[A[j][-1] - 1] += 1

		# print(cnt)

		var = max(cnt)
		ans = min(ans, var)
		ind = cnt.index(var)
		D[ind] = 0
		for j in range(N):
			while True:
				if D[A[j][-1] - 1] == 0:
					A[j].pop()
				else:
					break

	print(ans)

if __name__ == '__main__':
	main()

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



int main() {

string s;
rep(i,3){
	cin>>s[i];
}


if(s[0]=='A' && s[1]=='A'&& s[2]=='A')
	{cout<<"No"<<endl;}
else if(s[0]=='B' && s[1]=='B'&& s[2]=='B')
{
	cout<<"No"<<endl;
}
else{
	cout<<"Yes"<<endl;
}
  return 0;
}


Measured memory_bytes: 256
H, W = map(int, input().split())
a1 = []
for y in range(H):
    c = list(input())
    if '#' in c:
        a1.append(c)
a2 = list(zip(*a1))
a3 = []
for x in range(W):
    r = a2[x]
    if '#' in r:
        a3.append(r)
a4 = list(zip(*a3))
for r in a4:
    print(''.join(r))


Measured memory_bytes: 3316
import itertools
import math
import string
import collections
from collections import Counter
from collections import deque
import sys
sys.setrecursionlimit(2*10**5)
INF = 2**60


def readints():
    return list(map(int, input().split()))


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
A, B = map(int, input().split())
for i in range(1, B+1):
    if A*i % B == 0:
        print(A*i)
        break


Measured memory_bytes: 38768
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9 + 7;

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	string s; cin >> s;
	for (int i = 0; i < 4; ++i) cout << s[i];
	cout << ' ';
	for (int i = 4; i < s.length(); ++i) cout << s[i];
	cout << '\n';
	return 0;
}

Measured memory_bytes: 3580
#[allow(unused_imports)]
use std::cmp::{Ordering};

#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};

#[allow(unused_imports)]
use std::io::{stdin, stdout, BufWriter, Write};

#[allow(unused_imports)]
use std::iter::FromIterator;

#[allow(unused_macros)]
macro_rules! min {
    ($x: expr) => ($x);
    ($x: expr, $($z: expr),+) => {{
        std::cmp::min($x, min!($($z),*))
    }}
}

#[allow(unused_macros)]
macro_rules! max {
    ($x: expr) => ($x);
    ($x: expr, $($z: expr),+) => {{
        std::cmp::max($x, max!($($z),*))
    }}
}

#[allow(unused_macros)]
macro_rules! get { 
    ([$t: ty]) => { 
        { 
            let mut line = String::new(); 
            stdin().read_line(&mut line).unwrap(); 
            line.split_whitespace().map(|t|t.parse::<$t>().unwrap()).collect::<Vec<_>>()
        }
    };
    ([$t: ty];$n: expr) => {
        (0..$n).map(|_|get!([$t])).collect::<Vec<_>>()
    };
    ($t: ty) => {
        {
            let mut line = String::new();
            stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($($t: ty),*) => {
        { 
            let mut line = String::new();
            stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            ($(iter.next().unwrap().parse::<$t>().unwrap(),)*)
        }
    };
    ($t: ty; $n: expr) => {
        (0..$n).map(|_|get!($t)).collect::<Vec<_>>()
    };
    ($($t: ty),*; $n: expr) => {
        (0..$n).map(|_|get!($($t),*)).collect::<Vec<_>>()
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        #[cfg(debug_assertions)]
        writeln!(&mut std::io::stderr(), concat!("[DEBUG] ", $(stringify!($a), "={:?} "),*), $($a),*).unwrap();
    }
}

const BIG_STACK_SIZE: bool = true;

#[allow(dead_code)]
fn main() {
    use std::thread;
    if BIG_STACK_SIZE {
        thread::Builder::new()
            .stack_size(32 * 1024 * 1024)
            .name("solve".into())
            .spawn(solve)
            .unwrap()
            .join()
            .unwrap();
    } else {
        solve();
    }
}

fn solve() {
    let (n,k) = get!(usize, usize);
    let a = get!([usize]);

    let modulo = 1_000_000_007;
    let mut map = BTreeMap::new();
    for i in 0..n {
        let mut entry = map.entry(&a[i]).or_insert(0);
        for j in 0..n {
            if a[i] > a[j] {
                *entry += 1;
            }
        }
    }
    let mut count = 0usize;
    for i in 0..n {
        for j in (i+1)..n {
            if a[i] > a[j] {
                count += 1;
            }
        }
    }
    count *= k;
    count %= modulo;
    for (_, val) in map {
        count += val*(k*(k-1)/2%modulo)%modulo;
        count %= modulo;
    }
    println!("{}", count);
}


Measured memory_bytes: 8572
#include<cstdio>
#include<algorithm>
#define N 1000100
#define ll long long
#define mod (int)(1e9+7)
using namespace std;
int fac[N],inv[N],n;
int C(int n,int m)
{
	if(n<m)return 0;
	return (ll)fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int ans=0;
int main()
{
	scanf("%d",&n);
	fac[0]=1;
	for(int i=1;i<=n;i++)
	fac[i]=(ll)fac[i-1]*i%mod;
	inv[1]=1;
	for(int i=2;i<=n;i++)
	inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;
	inv[0]=1;
	for(int i=1;i<=n&&i<mod;i++)
	inv[i]=(ll)inv[i]*inv[i-1]%mod;
	for(int i=1;i<n;i++)
	{
		int now=C(i-1,n-i-1);
		ans=(ans+(ll)now*fac[i]%mod*fac[n-i-1]%mod)%mod;
	}
	printf("%d\n",(fac[n]+mod-ans)%mod);
}

Measured memory_bytes: 7936
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define L_T_S_K ;
const int N = 1e5;
const int mod = 1e9 + 7;
int binpow(int a, int b) {
    a %= mod;
    int res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int32_t main(){
 L_T_S_K;
 int n;
 cin >> n;
 double head[n];
 for(int i = 0 ; i < n ; i++){
 	cin >> head[i];
 }
 double dp[3001][3001]; 
 memset(dp , 0.0 , sizeof dp);
 dp[0][0] = 1.0;
 for(int i = 1 ; i <= n ; i++){
 	for(int j = 0 ; j <= i ; j++){
 		if(j == 0) dp[i][j] = dp[i - 1][j] * (1.0 - head[i - 1]);
 		else dp[i][j] = dp[i - 1][j] * (1.0 - head[i - 1])  + dp[i - 1][j - 1] * head[i -1]; 
 	}	
 }
 double ans = 0.0;
 for(int i = 0 ; i <= n ; i++){
 		if(i > n - i)ans+=dp[n][i];
 }
 cout << fixed << setprecision(10) << ans ;
return 0;
}

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

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> ii;

void solve (){
	int n;
	cin >> n;
	vector<int> a(n);
	ll ans = 0;
	for(int i = 0; i < n; i++)
		cin >> a[i];
	
	sort(a.begin(), a.end(), greater<int>());
	
	int it = 0, at = 0, cont = 1;
	while(it < n-1){
		ans += a[at];
		it++;
		at += (it & 1);
	}
	cout << ans << endl; 
}

int32_t main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	
	int tc = 1;
	//cin >> tc;
	while(tc--)
	
		solve();
}


Measured memory_bytes: 3964
S = input()
T = input()
ls = len(S)
lt = len(T)
cand = []
for i in range(ls-lt+1):
    frac =  S[i:i+lt]
    if all(map(lambda x:x[0]==x[1] or x[0]=='?',zip(frac, T))):
        cand.append(S[0:i]+T+S[i+lt:ls])
if cand == []:
    print("UNRESTORABLE")
else:
    cand = list(map(lambda x:x.replace('?','a'), cand))
    print(sorted(cand)[0])

Measured memory_bytes: 3064
package main

import (
	"fmt"
)

func main() {
	var n int
	fmt.Scan(&n)
	a := make([]int, n)
	for i := range a {
		fmt.Scan(&a[i])
	}

	count := 0
	next := 1
	for _, ai := range a {
		if ai == next {
			next++
			continue
		}
		count++
	}
	if count == n {
		fmt.Println(-1)
	} else {
		fmt.Println(count)
	}

}


Measured memory_bytes: 5632
// F*** the exam

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long int
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define pll pair<ll,ll>
#define mp make_pair
#define bp __builtin_popcountll
#define MOD  1000000007
const int N = 200005;
#define FAST ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);srand(time(NULL));

void solve()
{
    ll x,n;
    cin >> x >> n;
    map<ll,ll> y;
    for(ll i=0,x;i<n;i++)
    {
        cin >> x;
        y[x]++;
    }
    ll cnt = 0;
    while(1)
    {
        ll left = x - cnt;
        if(y.find(left)==y.end())   
        {
            cout<<left;
            return;
        }
        left = x + cnt;
        if(y.find(left)==y.end())   
        {
            cout<<left;
            return;
        }
        cnt++;
    }
}

int main()
{
    FAST;
    ll t = 1;
 //   cin >> t;
    while(t--)
    {
        solve();
    }
}

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

using namespace std;

#define ll long long
#define pb push_back
#define vi vector<int>
#define bn(n) (n).begin(), (n).end()
#define FOR(n) for(int i = 0; i < (int)n; i++)


void solve() {
    string a, b;
    cin >> a >> b;
    if (a.length() != b.length()) {
        cout << (a.length() > b.length() ? "GREATER" : "LESS") << "\n";
        return;
    } else {
        for (int i = 0 ; i < a.length(); i++) {
            if (a[i] != b[i]) {
                cout << (a[i] > b[i] ? "GREATER" : "LESS") << "\n";
                return;
            }
        }
        cout << "EQUAL\n";
    }
}

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

    int t = 1, i = 1;
    //cin >> t;
    while(t--) {
        //cout << "Case #" << i << ": ";
        solve();
        //i++;
    }
    return 0;
}


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

#define REP(i, n) for(ll i = 0; i < n; i++)
#define ALL(x) (x).begin(),(x).end()
#define MSG(x) cout << x << endl;
#define YN(x) x ? cout << "YES" << endl : cout << "NO" << endl;
#define Yn(x) x ? cout << "Yes" << endl : cout << "No" << endl;
#define yn(x) x ? cout << "yes" << endl : cout << "no" << endl;

using namespace std;
using ll = long long;
const static ll MOD = 1e9 + 7;

int main(int argc, char *argv[]) {
    string s;
    cin >> s;
    MSG(s.substr(0, 4) + " " + s.substr(4))
}


Measured memory_bytes: 256
using System;

class Program
{
    public static void Main(string[] args)
    {
        int N, Q;
        string S;
        int[] ls;
        int[] rs;
        {
            {
                var nq = Console.ReadLine().Split(' ');
                N = int.Parse(nq[0]);
                Q = int.Parse(nq[1]);
            }
            S = Console.ReadLine();
            ls = new int[Q];
            rs = new int[Q];
            for (int i = 0; i < Q; i++)
            {
                {
                    var lr = Console.ReadLine().Split(' ');
                    ls[i] = int.Parse(lr[0]);
                    rs[i] = int.Parse(lr[1]);
                }
            }
        }

        int[] r = new int[S.Length + 1];
        {
            for (int i = 0; i < S.Length - "AC".Length + 1; i++)
            {
                r[i + 1] = r[i] + (S.Substring(i, 2) == "AC" ? 1 : 0);
            }
            for (int i = S.Length - "AC".Length + 1; i < S.Length; i++)
                r[i + 1] = r[i];
        }

        for (int i = 0; i < Q; i++)
        {
            Console.WriteLine(r[rs[i] - 1] - r[ls[i] - 1]);
        }
    }
}

Measured memory_bytes: 17092
# B - Foods Loved by Everyone
from collections import deque
N,M = map(int,input().split())
K = []
A = []
for o in range(N):
    KA = deque(list(map(int,input().split())))
    Ki = KA.popleft()
    K.append(Ki)
    A.append(list(KA))

common = [0]*(M+1)
for i in A:
    for j in i:
        common[j] += 1
count = 0
for k in common:
    if k == N:
        count += 1
print(count)    

Measured memory_bytes: 65648
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#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 REP(i, n) FOR(i, 0, (n))
#define REPR(i, n) FORR(i, (n) - 1, 0)
#define REP1(i, n) FOR(i, 1, (n) + 1)
#define REPS(c, s) for (char c : s)
#define ALL(c) (c).begin(), (c).end()
#define SORT(c) sort(ALL(c))
#define REV(c) reverse(ALL(c))
#define sz(v) (int)v.size()
#define endl '\n'
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
template<class T> inline void printv(vector<T>& v) {int n = sz(v); REP(i, n) cout << v[i] << (i == n - 1 ? endl : ' ');}
template<class T> inline void printlnv(vector<T>& v) {int n = sz(v); REP(i, n) cout << v[i] << endl;}
const int MOD = 1000000007;
const int INF = 1000000001;
const ll LINF = 1000000001000000001LL;
 
void solve();
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(numeric_limits<double>::max_digits10);
    solve();
    return 0;
}

void solve() {
    int n;
    cin >> n;

    function<void(string, char)> dfs = [&](string s, char mx) {
        if (sz(s) == n) {
            cout << s << endl;
        } else {
            for (char c = 'a'; c <= mx; c++) {
                dfs(s + c, ((c == mx) ? (char)(mx + 1) : mx));
            }
        }
    };

    dfs("", 'a');
}


Measured memory_bytes: 1536
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
	static int n, m, k;
	static int[] u, v;
	static int[] w;
	static char[] l;

	static class Edge implements Comparable<Edge> {
		int src, dst;
		int cost;
		char c;

		public Edge(int src, int dst, int cost, char c) {
			this.src = src;
			this.dst = dst;
			this.cost = cost;
			this.c = c;
		}

		public int compareTo(Edge o) {
			if (cost != o.cost)
				return Integer.compare(cost, o.cost);
			else {
				return c - o.c;
			}
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (true) {
			n = sc.nextInt();
			m = sc.nextInt();
			k = sc.nextInt();
			if (n == 0 && m == 0 && k == 0)
				break;
			u = new int[m];
			v = new int[m];
			w = new int[m];
			l = new char[m];
			DJSet ds = new DJSet(n);
			for (int i = 0; i < m; ++i) {
				u[i] = sc.nextInt() - 1;
				v[i] = sc.nextInt() - 1;
				w[i] = sc.nextInt();
				l[i] = sc.next().toCharArray()[0];
				ds.setUnion(u[i], v[i]);
			}
			if (ds.upper[ds.root(0)] != -n) {
				System.out.println(-1);
				continue;
			}
			int left = -1 << 20;
			int right = 1 << 20;
			while (right - left > 1) {
				int middle = (right + left) / 2;
				int[] ret = kruskal(middle);
				if (ret[1] >= k) {
					left = middle;
				} else {
					right = middle;
				}
			}
			int[] ret1 = kruskal(right);
			int[] ret2 = kruskal(left);
			if (!(ret1[1] <= k && k <= ret2[1])) {
				System.out.println(-1);
			} else
				System.out.println(ret2[0]);
		}
	}

	static int[] kruskal(int add) {
		PriorityQueue<Edge> que = new PriorityQueue<Main.Edge>();
		for (int i = 0; i < m; ++i) {
			Edge e = new Edge(u[i], v[i], w[i], l[i]);
			if (l[i] == 'A')
				e.cost += add;
			que.add(e);
		}

		DJSet ds = new DJSet(n);
		int weight = 0;
		int cnt = 0;
		while (!que.isEmpty()) {
			Edge e = que.poll();
			if (ds.equiv(e.src, e.dst))
				continue;
			weight += e.cost;
			ds.setUnion(e.src, e.dst);
			if (e.c == 'A') {
				++cnt;
			}
		}
		return new int[] { weight - k * add, cnt };
	}

	static class DJSet {
		int n;
		int[] upper;

		public DJSet(int n) {
			this.n = n;
			upper = new int[n];
			Arrays.fill(upper, -1);
		}

		boolean equiv(int x, int y) {
			return root(x) == root(y);
		}

		int root(int x) {
			return upper[x] < 0 ? x : (upper[x] = root(upper[x]));
		}

		void setUnion(int x, int y) {
			x = root(x);
			y = root(y);
			if (x == y)
				return;
			if (upper[x] > upper[y]) {
				int tmp = x;
				x = y;
				y = tmp;
			}
			upper[x] += upper[y];
			upper[y] = x;
		}
	}

	static void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}

}

Measured memory_bytes: 68484
# import copy

# N = list(map(int,input().split(' ')))
# X =[input() for i in range(N[0])] 

def p(X):
    print(X)
N = int(input())
S = list(map(int, input().split()))
count = 0
for i in range(len(S)-2):
    for j in range(i+1,len(S)-1):
        for k in range(j+1,len(S)):
            result = [S[i],S[j],S[k]]
            re = sorted(result,reverse=True)
            if (S[i] != S[j] and S[i] != S[k] and S[j] !=S[k]) and (re[0]< re[1]+re[2]):
                count +=1

p(count)



Measured memory_bytes: 9212
# 9or8で埋めたやつが強い あるいはオリジナル
# 桁を一つ落として（1なら9999...）残りを9で埋める
# オリジナルはたとえば199とかのとき19が最大になる

s = input()
tmp = 0
for i in s:
    tmp += int(i)
if s[0] == "1":
    print(max(9 * (len(s) - 1), tmp))
else:
    print(max(int(s[0]) - 1 + 9 * (len(s) - 1), tmp))



Measured memory_bytes: 2940
#include <algorithm>
#include <climits>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <vector>
#include <cmath>

#define int long long int
constexpr int INF = std::numeric_limits<int>::max();
constexpr int NINF = std::numeric_limits<int>::min();
using namespace std;


void solve() {
  int N;
  cin >> N;

  int ans = 0;
  for (int i = 1; i <= N; i++) {
    int y = N/i;
    ans += y*(y+1)*i/2;
  }

  cout << ans << endl;
}

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


Measured memory_bytes: 3152
#include<iostream>
using namespace std;
 
bool overlap(int a, int b, int c, int d){
  if ( d <= a ) return false;
  if ( b <= c ) return false;
  return true;
}
 
main(){
  int a, b, s, f, n;
  cin >> a >> b >> n;
  for ( int i = 0; i < n; i++ ){
    cin >> s >> f;
    if ( overlap(a, b, s, f) ){
      cout << 1 << endl;
      return 0;
    }
  }
  cout << 0 << endl;
  return 0;
}


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

namespace AtCoder
{
    class Solver
    {
        private const int M = 1000000007;
        private readonly int N;
        private readonly int L;
        private readonly int R;
        private long[] m_facs;
        public Solver(int n, int[] A)
        {
            N = n;
            int[] order = Enumerable.Repeat(-1, n + 2).ToArray();
            for (int i = 0; i < n + 1; ++i)
            {
                if (order[A[i]] < 0)
                {
                    order[A[i]] = i;
                }
                else
                {
                    L = order[A[i]];
                    R = n - i - 1;
                    break;
                }
            }
            m_facs = new long[n + 1];
            m_facs[0] = 1;
            for (int i = 1; i <= n; ++i)
            {
                m_facs[i] = (m_facs[i - 1] * i) % M;
            }
        }
        private static long Pow(long a, int m)
        {
            switch (m)
            {
            case 0: return 1;
            case 1: return a;
            }
            long p = Pow(a, m / 2);
            if ((m & 1) == 0)
            {
                return p * p % M;
            }
            else
            {
                return (p * p % M) * a % M;
            }
        }
        private long Ncr(int n, int r)
        {
            if (n < r) { return 0; }
            if (n == r) { return 1; }
            long res = m_facs[n];
            res *= Pow(m_facs[r], M - 2);
            res %= M;
            res *= Pow(m_facs[n - r], M - 2);
            res %= M;
            return res;
        }
        public long Solve(int k)
        {
            int n = L + R + 1;
            return ((Ncr(N, k) - (Ncr(n, k) - Ncr(n - 1, k))) % M + M) % M;
        }
    }
    class Program
    {
        private const int M = 1000000007;
        private static string Read() { return Console.ReadLine(); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }

        static void Main(string[] args)
        {
            int n = ReadInt();
            int[] A = ReadInts();
            var solver = new Solver(n + 1, A);
            for (int i = 1; i <= n + 1; ++i)
            {
                Console.WriteLine(solver.Solve(i));
            }
        }
    }
}


Measured memory_bytes: 27356
def sieve(MAX):
    list=[True]*(MAX+1)
    prime=[]
    for i in range(2,MAX+1):
        if list[i]:
            prime.append(i)
            for j in range(i,MAX+1,i):  list[j]=False
    return prime

def main():
    prime=sieve(10000)
    while True:
        N=int(raw_input())
        if(N==0):   break
        ans=0
        for i in range(len(prime)):
            if prime[i]>=N:
                if prime[i]==N: ans+=1
                break
            tmp=prime[i]
            for j in range(i+1,len(prime)):
                tmp+=prime[j]
                if tmp>=N:
                    if tmp==N:  ans+=1
                    break
        print ans

if __name__=='__main__':    main();

Measured memory_bytes: 18000
n, m = map(int, input().split())
a = list(map(int, input().split()))
r = [1 for _ in range(n)]
s = sum(a)
for i in range(n):
    if a[i]<s/(4*m):
        r[i] = 0
if sum(r)<m:
    print("No")
else:
    print("Yes")

Measured memory_bytes: 9068
/*input

*/
#include <bits/stdc++.h>
#define up(i,a,b) for(int (i) = (a);(i)<=(b);++(i))
#define down(i,b,a) for(int (i) = (b);i>=(a);--i)
#define debug(x) cerr << (x) << '\n';
#define bits(x,i) ((x >> i) & 1)
#define mid ((l+r)/2)
#define pr pair<int,int>
using namespace std;
string n;
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	int s = 0;
	for(int i=0;i<n.size();++i) s = (s + n[i] - '0') % 9;
	cout << (s % 9 == 0 ? "Yes" : "No");
}

Measured memory_bytes: 3820
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define fs first
#define sc second
typedef pair<ll, ll> l_l;
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
int ni(int x){
  int cnt=0;
  while(x%2==0){
    x/=2;
    cnt++;
  }
  return cnt;
}
int main(){
  int n;
  cin>>n;
  int cnt=0; int ans;
  for(int i=1;i<=n;i++){
    if(cnt<=ni(i)){
      cnt=ni(i);
      ans=i;
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define re return
using namespace std;
int main()
{
	int a1,a2;
	string s1,s2,u;
	cin>>s1>>s2>>a1>>a2>>u;
	if (u==s1)  a1--;
	if (u==s2)  a2--;
	cout<<a1<<' '<<a2; 
	re 0;
}

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

static const int MOD = 1000000007;

int main() {
    int N;
    cin >> N;
    long long sum, A[N];
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        sum = (sum + A[i]) % MOD;
    }

    // sum = A1 + A2 + ... + An
    // A1(A2+A3+...+An) + A2(A3+A4+...+An) + ... + An-2(An-1+An) + An-1An
    long long ans = 0;
    for (int i = 0; i < N - 1; i++) {
        sum -= A[i];
        if (sum < 0) sum += MOD;

        ans += A[i] * sum;
        ans %= MOD;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 5072
#include <iostream>

using namespace std;

int main()
{
    int RPS[5], R, P, S;
    while (1) {
	R = P = S = 0;
	for (int i = 0; i < 5; i++) {
            cin >> RPS[i];
            if (RPS[0] == 0) break;
            if (RPS[i] == 1) R++;
            else if (RPS[i] == 2) S++;
            else P++;
        }
	if (RPS[0] == 0) break;
        
	if ((R > 0 && S > 0 && P > 0) || R == 5 || S == 5|| P == 5) {
            for (int i = 0; i < 5; i++) {
                cout << "3" << endl;
            }
        } else if (R == 0) {
            for (int i = 0; i < 5; i++) {
                if (RPS[i] == 2) {
                    cout<<"1"<<endl;
                } else {
                    cout<<"2"<<endl;
                }
            }
        } else if (S == 0) {
            for (int i = 0; i < 5; i++) {
                if (RPS[i] == 3) {
                    cout << "1" << endl;
                } else {
                    cout << "2" << endl;
                }
            }
        } else if (P == 0) {
            for (int i = 0; i < 5; i++) {
                if (RPS[i] == 1) {
                    cout << "1" << endl;
                } else {
                    cout << "2" << endl;
                }
            }
        }
    }
    return 0;
}

Measured memory_bytes: 3020
#include <iostream>

int main(){

    int H, W, x, y, r;
    
    std::cin>>W>>H>>x>>y>>r;
    
    if((x-r)>=0 && (x+r)<=W && (y-r)>=0 && (y+r)<=H)
        std::cout << "Yes" << std::endl;
    else
        std::cout << "No" << std::endl;

    return 0;
}

Measured memory_bytes: 3092
from math import factorial

n = int(input())
s_dict = {}
for i in range(n):
  s = "".join(sorted(list(input())))
  if s in s_dict:
    s_dict[s] += 1
  else:
  	s_dict[s] = 1
  
count = 0
for v in s_dict.values():
  if v > 1:
    count += factorial(v) // (factorial(2) * factorial(v - 2))

print(count)

Measured memory_bytes: 17932
import math
a=input()
b=len(a)
re=[0 for i in range(b)]
i=0
r=1
l=0
for i in range(b):
  if a[i]=="R":
    if a[i]==a[i+1]:
      r+=1
    else:
      rr=math.ceil(r/2)
      re[i]+=rr
      re[i+1]+=r-rr
      r=0
      l+=1
      rl=i
  if a[i]=="L":
    if i==b-1:
      c=i-rl
      lr=math.ceil(l/2)
      re[rl+1]+=lr
      re[rl]+=l-lr
    else:
      if a[i]==a[i+1]:
        l+=1
      else:
        lr=math.ceil(l/2)
        re[rl+1]+=lr
        re[rl]+=l-lr
        l=0
        r+=1
print(" ".join(map(str,re)))
        
  

Measured memory_bytes: 10492
#include<bits/stdc++.h>
using namespace std;
#define rep(i ,a, n) for (long long int i=a;i<=n;i++)
#define pb  push_back
#define mp make_pair
#define fp first
#define sp second
#define be(v) v.begin(),v.end()
typedef long long ll;
typedef vector<ll> vi ;
typedef vector<pair<ll , ll > >  vpi ;
const int ma1=3e5+5;
string no="NO",yes="YES";
#define MOD 1000000007
int max_char=26;
vector<ll> v;
int main()
{
      ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll t=1;
    while(t--)
    {
        ll n,m;
        cin>>n>>m;
        ll a[n];
        for(int i=0;i<n;i++)
        cin>>a[i];
        if(n-1<=m)
        {
            cout<<abs(a[0]-a[n-1]);
            return 0;
        }
        ll dp[n];
        dp[0]=0;
        for(int i=1;i<=m;i++)
            {
                dp[i]=abs(a[i]-a[0]);

        }
        for(int i=m+1;i<n;i++)
        {
            dp[i]=INT_MAX;
            for(int j=i-1;j>=i-m;j--)
            {
              ll  x=dp[j]+abs(a[i]-a[j]);
                dp[i]=min(x,dp[i]);
            }
        }
        cout<<dp[n-1];
    }
    return 0;
}
















Measured memory_bytes: 5112
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#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;
typedef long long ll;

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

    int n;
    cin >> n;

    int pay = 1000;
    while(pay < n) pay += 1000;

    cout << pay - n << endl;

    return 0;
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define rep1(i,n) for(int i=1;i<=(int)n;i++)
#define sp(n) cout << fixed << setprecision(n)
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; }
typedef long long ll;
using namespace std;
int main(void){
    ll n,m;cin>>n>>m;
    vector<ll> a(n);
    rep(i,n) cin>>a[i];
    a[0]%=m;
    rep(i,n-1){
        a[i+1]+=a[i];
        a[i+1]%=m;
    }
    map<ll,ll> mp;
    ll res=0;
    rep(i,n){
        res+=mp[a[i]];
        mp[a[i]]++;
        if(a[i]==0)res++;
    }
    cout<<res<<endl;
}

Measured memory_bytes: 7988
'use strict';
console.log(function(args){
  const tmp = args.trim().split('\n');
  const N = tmp[0]|0;
  const x = [], y = [];
  for ( let i = 0; i < N; i++ ) {
    const cood = tmp[i+1].split(' ').map(v=>v|0);
    x[i] = cood[0], y[i] = cood[1];
  }
  let sumL = 0, nL = 0.0;
  function travel(trail,length,current) {
    for ( let next = 0; next < N; next++ ) {
      if ( trail & 1<<next ) continue;
      const l = Math.sqrt(Math.pow(x[current]-x[next],2.0)+Math.pow(y[current]-y[next],2.0));
      if ( (trail|1<<next) === (1<<N)-1 ) {
        sumL += length+l; nL=nL+1.0;
        return;
      }
      travel(trail|1<<next,length+l,next);
    }
  }
  for ( let i = 0; i < N; i++ ) {
    travel(1<<i,0.0,i);
  }
  return (sumL/nL).toString();
}(require('fs').readFileSync('/dev/stdin', 'utf8')));


Measured memory_bytes: 14156
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,x,n) for(int i=x; i<(n); i++)
#define ALL(n) begin(n),end(n)
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long Int;
typedef pair<Int, Int> P;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;


int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    vector<vector<int>> edge(110);
    int n; cin>>n;
    for(int i=0; i<n; i++)
    {
        int u; cin>>u;
        u--;
        int k; cin>>k;
        if(k!=0) {
        for(int j=0; j<k; j++){
            int v; cin>>v;
            v--;
            edge[u].push_back(v);
        }
    }
    }
    for(int i=0; i<n; i++){
        vector<int> ans(n,0);
        for(int j=0; j<edge[i].size(); j++){
            ans[edge[i][j]]++;
        }
        for(int k=0; k<n; k++){
            cout<<ans[k]<<(k==n-1?'\n':' ');
        }
    }
    return 0;
}


Measured memory_bytes: 3236
#include <stdio.h>
#include <string.h>

int main(){
  char x[1000];
  unsigned int i,a=0;
  
  while(1){
    scanf("%s",x);
    if(strcmp(x,"0")==0) break;

    a=0;
    for(i=0; i<strlen(x); ++i){
      if(x[i]!='0'){
	x[i]-='0';
	a+=x[i];
      }
    }
    printf("%d",a);
    printf("\n");
  }

  
  return 0;
}



Measured memory_bytes: 2744
n = int(input())
a = list(map(int, input().split()))
q = int(input())
data = [0]*(10**5+1)
ans = sum(a)
for i in a:
    data[i] += 1

for j in range(q):
    b, c = map(int, input().split())
    ans = ans +(c-b)*data[b]
    data[c] = data[c] + data[b]
    data[b] = 0
    print(ans)
    # print(data[0:5])



Measured memory_bytes: 20880
#include<stdio.h>
int main(){
    int i, n, m, a, b, c[50]={0};
    scanf("%d %d", &n, &m);
    for(i=0; i<m; i++){
        scanf("%d %d", &a, &b);
        c[a-1]+=1;
        c[b-1]+=1;
    }
    for(i=0; i<n; i++)printf("%d\n", c[i]);
    return 0;
}

Measured memory_bytes: 128
package main

import (
	"fmt"
)

func main() {
    var n int
    fmt.Scanf("%d", &n)

	var count int = 0
	for a:=1; a<n ; a++{
		var b_max = int((n-1) / a)
		for b:=1; b<=b_max; b++{
			if a * b < n{
				count = count+1
			}
		}
	}

    fmt.Printf("%d\n", count)
}


Measured memory_bytes: 1864
#include<stdio.h>

int main()
{
    int a,b,n=0;

    scanf("%d%d",&a,&b);

    if(a>b)
    {
        a=a+b;
        b=a-b;
        a=a-b;
    }

    for(int i=0;i<b;i++)
        n=n*10+a;

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

    return 0;
}


Measured memory_bytes: 128
//by yjz
#include<bits/stdc++.h>
using namespace std;
#define FF first
#define SS second
#define PB push_back
#define MP make_pair
typedef long long ll;
const int Imx=2147483647;
const int mod=1000000007;
const ll Lbg=2e18;
int n,m,k;
ll dp[4011],ndp[4011];
int main()
{
	cin>>n>>m>>k;
	dp[0]=1;
	ll ans=0;
	for(int i=1;i<=(n+m-1)/(k-1);i++)
	{
		memset(ndp,0,sizeof(ndp));
		int sz=i*(k-1)+1;
		for(int j=0;j<=sz;j++)
		{
			for(int t=1;t<k&&t<=j;t++)ndp[j]+=dp[j-t];
			ndp[j]%=mod;
		}
		for(int j=1;j<=sz;j++)
		{
			if(j<=n&&sz-j<=m&&(n-j)%(k-1)==0)ans+=ndp[j];
		}
		ans%=mod;
		for(int j=0;j<=sz;j++)ndp[j]=(ndp[j]+dp[j])%mod;
		swap(ndp,dp);
	}
	cout<<ans%mod<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int maxi, sum;
	int n, v, i;

	scanf("%d", &n);
	while (n--){
		maxi = sum = 0;
		for (i = 0; i < 3; i++){
			scanf("%d", &v);
			v *= v;
			sum += v;
			maxi = fmax(maxi, v);
		}
		puts (maxi * 2 - sum ? "NO" : "YES"); 
	}
	return (0);
}

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

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define Debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long LL;
typedef long double LD;
typedef unsigned int uint;
typedef pair <int, int> pii;
typedef unsigned long long uLL;

template <typename T> inline void Read(T &x) {
  char c = getchar();
  bool f = false;
  for (x = 0; !isdigit(c); c = getchar()) {
    if (c == '-') {
      f = true;
    }
  }
  for (; isdigit(c); c = getchar()) {
    x = x * 10 + c - '0';
  }
  if (f) {
    x = -x;
  }
}

template <typename T> inline bool CheckMax(T &a, const T &b) {
  return a < b ? a = b, true : false;
}

template <typename T> inline bool CheckMin(T &a, const T &b) {
  return a > b ? a = b, true : false;
}

const int N = 100005;

int n, m, a[N], f[N], p[N];
priority_queue <pii> q;
vector <int> v[N];
LL ans;

inline int F(int x) {
  while (x != f[x]) {
    x = f[x] = f[f[x]];
  }
  return x;
}

int main() {
#ifdef wxh010910
  freopen("d.in", "r", stdin);
#endif
  Read(n), Read(m);
  for (int i = 0; i < n; ++i) {
    Read(a[i]), f[i] = i;
  }
  for (int i = 0, x, y; i < m; ++i) {
    Read(x), Read(y);
    f[F(x)] = F(y);
  }
  int c = 0;
  for (int i = 0; i < n; ++i) {
    if (F(i) == i) {
      ++c;
    }
    v[F(i)].pb(i);
  }
  if (2 * (c - 1) > n) {
    puts("Impossible");
  } else if (c == 1) {
    puts("0");
  } else {
    a[n] = 1 << 30;
    for (int i = 0; i < n; ++i) {
      if (F(i) == i) {
        sort(v[i].begin(), v[i].end(), [&](const int &x, const int &y) {
            return a[x] < a[y];
            });
        v[i].pb(n), p[i] = 1, ans += a[v[i][0]], q.push(mp(-a[v[i][1]], i));
      }
    }
    for (c -= 2; c; --c) {
      pii x = q.top();
      q.pop(), ans -= x.X, ++p[x.Y], q.push(mp(-a[v[x.Y][p[x.Y]]], x.Y));
    }
    printf("%lld\n", ans);
  }
#ifdef wxh010910
  Debug("My Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC);
#endif
  return 0;
}


Measured memory_bytes: 6528
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
int h,n,a,b,c[11005];
int main(){
	scanf("%d%d", &h, &n);
	fill(c+1,c+h+1,(int)1e9);
	rep(i,n){
		scanf("%d%d", &a, &b);
		rep(j,h+1) c[j] = min(c[j],(j>a?c[j-a]:0)+b);
	}
	printf("%d\n", c[h]);
}

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

const ll MOD = 1000000007;

struct mint {
    ll x;
    mint(ll x = 0) : x((x % MOD + MOD) % MOD) {
    }
    mint operator-() const {
        return mint(-x);
    }
    mint &operator+=(const mint a) {
        if ((x += a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint &operator-=(const mint a) {
        if ((x += MOD - a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint &operator*=(const mint a) {
        (x *= a.x) %= MOD;
        return *this;
    }
    mint operator+(const mint a) const {
        mint res(*this);
        return res += a;
    }
    mint operator-(const mint a) const {
        mint res(*this);
        return res -= a;
    }
    mint operator*(const mint a) const {
        mint res(*this);
        return res *= a;
    }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t / 2);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }

    // for prime MOD
    mint inv() const {
        return pow(MOD - 2);
    }
    mint &operator/=(const mint a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint a) const {
        mint res(*this);
        return res /= a;
    }
};

ostream &operator<<(ostream &os, const mint &a) {
    return os << a.x;
}

vector<vector<int>> G;
int K;

mint dfs(int n, int p) {
    mint k;
    if(p==-1) k=K-1;
    else k=K-2;

    mint ans = 1;
    for (auto e : G[n]) {
        if (e == p) continue;
        ans = ans * k * dfs(e, n);
        k = k -1;
    }
    return ans;
}

int main() {
    int N;
    cin >> N >> K;
    G.resize(N);
    rep(i, N - 1) {
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    cout << (mint)K*dfs(0, -1) << endl;
}

Measured memory_bytes: 11520
#include <bits/stdc++.h>
#include <math.h>
#include <cmath>

using namespace std;
using ll =long long;
using vi = vector<int>; 
using vvi = vector<vi>; 
using vl = vector<ll>; 
using vvl = vector<vl>; 

#define rep(i,n) ;for( int i =0; i < n ; i ++)

bool is_int_lround(double x){
  return std::lround(x)==x;
}
int ketasuu(int x){
  int n=0;
  while(x>0){
    x /=10 ;
    n ++;
  }
  return n;
}
ll gcd11(ll x, ll y){
  long long a= max(x,y), b=min(x,y), c=a%b;
  while( c!=0){
    a =b;
    b =c;
    c = a%b;
  }
  return b;
}

int abs(int x, int y){
  if(x>=y){
    return x-y;
  }
  else if(y>x){
    return y-x;
  }
}
int fiv(int n){
  if(n==0){
    return 0;
  }
  else if(n==1){
    return 1;
  }
  return fiv(n-1)+fiv(n-2);
}
ll conbi(int n,int m){
  
  cin>>n>>m;
  vector<ll> a(100);
  a[0] =1;
  for(int i=0;i<14;i++){
    a[i+1]=a[i]*(i+1);
  }
  return a[n] /(a[m] *a[n-m]);
}
int main(){
  string s;
  cin>>s;
  if(s =="AAA" || s== "BBB"){
    cout <<"No"<<endl;
  }
  else{
    cout <<"Yes"<<endl;
  }
 
  

  
}



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

int main(void){
    int r,c;
    std::cin>>r>>c;
    std::vector<std::vector<int>> data(r,std::vector<int>(c,0));
    int i,j;
    for(i=0;i<r;i++){
        int sum=0;
        for(j=0;j<c;j++){
            std::cin>>data[i][j];
            sum+=data[i][j];
        }
        data[i].push_back(sum);
    }
    for(i=0;i<r;i++){
        for(j=0;j<c+1;j++){
            std::cout<<data[i][j];
            if(j!=c)std::cout<<" ";
        }
        std::cout<<std::endl;
    }
    for(i=0;i<c+1;i++){
        int sum=0;
        for(j=0;j<r;j++){
            sum+=data[j][i];
        }
        std::cout<<sum;
        if(i!=c)std::cout<<" ";
    }
    std::cout<<std::endl;
    return 0;
}

Measured memory_bytes: 3140
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using static System.Console;

class Program
{
    static void Main(string[] args)
    {
        new Program().Calc();
    }

    Scanner cin;

    public Program() { }

    bool chmax<T>(ref T a, T b) where T : IComparable<T> { if (a.CompareTo(b) < 0) { a = b; return true; } return false; }
    bool chmin<T>(ref T a, T b) where T : IComparable<T> { if (b.CompareTo(a) < 0) { a = b; return true; } return false; }

    void Calc()
    {
        cin = new Scanner();

        string S = cin.next();
        int sLength = S.Length;
        S += "\0";

        char[] arr = new char[sLength];

        int index = 0;

        for (int i = 0; i < sLength; ++i)
        {
            if (S[i] == 'B' && S[i+1] == 'C')
            {
                arr[index++] = 'D';
                ++i;
            }
            else
            {
                arr[index++] = S[i];
            }
        }

        long count = 0;
        int aCount = 0;

        for (int i = 0; i < sLength; ++i)
        {
            if (arr[i] == 0)
            {
                break;
            }
            else if (arr[i] == 'A')
            {
                ++aCount;
            }
            else if (arr[i] == 'D')
            {
                count += aCount;
            }
            else
            {
                aCount = 0;
            }
        }

        WriteLine(count);
    }
}

public static class StringExtension
{
    public static char GetChar1(this string str, int indexOneBase)
    {
        return str[indexOneBase - 1];
    }
}

class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    public string next()
    {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return next();
        i = 0;
        return s[i++];
    }

    public int nextInt()
    {
        return int.Parse(next());
    }
    public int[] ArrayInt(int N, int add = 0)
    {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextInt() + add;
        }
        return Array;
    }

    public long nextLong()
    {
        return long.Parse(next());
    }

    public long[] ArrayLong(int N, long add = 0)
    {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextLong() + add;
        }
        return Array;
    }

    public double nextDouble()
    {
        return double.Parse(next());
    }


    public double[] ArrayDouble(int N, double add = 0)
    {
        double[] Array = new double[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextDouble() + add;
        }
        return Array;
    }
}


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

using namespace std;
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
constexpr int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
constexpr int dy[] = {0, -1, 0, 1, 1, -1, -1, 1};

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){os << "["; for (const auto &v : vec) {os << v << ","; } os << "]"; return os; }
template <typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &p) {os << "(" << p.first << ", " << p.second << ")"; return os;}

void solve() {
    int N;
    cin >> N;
    vector<ll> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    int k = max_element(all(A)) - A.begin();
    ll sum = 0;
    for (int i = 0; i < N; i++) {
        if (i == k) {
            sum += A[i] / 2;
        } else {
            sum += A[i];
        }
    }
    cout << sum << endl;
}

int main() {
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    solve();
    return 0;
}

Measured memory_bytes: 256