akhauriyash/Code-Regression huggingface dataset:
using System;
using System.IO;
using System.Linq;
using CompLib.Util;

public class Program
{
    public void Solve()
    {
        var sc = new Scanner();
        int n = sc.NextInt();
        int k = sc.NextInt();
        double[] logA = sc.DoubleArray().Select(Math.Log10).ToArray();
        double sum = 0;
        for (int i = 0; i < k; i++)
        {
            sum += logA[i];
        }

        Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) {AutoFlush = false});
        for (int i = k; i < n; i++)
        {
            double next = sum + logA[i] - logA[i - k];
            Console.WriteLine(sum < next ? "Yes" : "No");
            sum = next;
        }

        Console.Out.Flush();
    }

    public static void Main(string[] args) => new Program().Solve();
}

namespace CompLib.Util
{
    using System;
    using System.Linq;

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

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

        public string Next()
        {
            if (_index >= _line.Length)
            {
                string s;
                do
                {
                    s = Console.ReadLine();
                } while (s.Length == 0);

                _line = s.Split(Separator);
                _index = 0;
            }

            return _line[_index++];
        }

        public string ReadLine()
        {
            _index = _line.Length;
            return Console.ReadLine();
        }

        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()
        {
            string s = Console.ReadLine();
            _line = s.Length == 0 ? new string[0] : s.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: 49088
#include <bits/stdc++.h>
using namespace std;

int main() {
  long long N, T;
  cin >> N >> T;
  long long t, total, lt, prevt;
  cin >> t;
  prevt = lt = t;
  for (long long i=1; i<N; i++) {
    cin >> t;
    if (prevt + T < t) {
      total += (prevt - lt) + T;
      lt = t;
    }
    prevt = t;
  }
  total += (t - lt) + T;
  cout << total << endl;
}

Measured memory_bytes: 256
/**
*Keep
**Moving
***Forward
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
#define f( i , x , n ) for(int i = x; i < (int)(n); ++i)
#define pb push_back
#define all(c) (c).begin(),(c).end()

int F[100005];

int main(){
    int n;
    cin >> n;
    int mx = 0;
    for(int i=0;i<n;i++){
        int x;
        cin >> x;
        F[x]++;
        mx = max(mx,x);
    }
    int mxc = 1;
    for(int i=0;i<=mx;i++){
        if(i==0)mxc = max(mxc,F[i+1]+F[i]);
        else if(i==mx)mxc = max(mxc,F[i-1]+F[i]);
        else mxc = max(mxc,F[i-1]+F[i+1]+F[i]);
    }
    cout << mxc;
    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
using i64 = int64_t;

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

    i64 cnt[3] = { 0 };
    for (auto&& c : s) {
        cnt[c % 3]++;
    }

    i64 res = cnt[0] * cnt[1] * cnt[2];

    for (int j = 0; j < n; j++) {
        for (int i = 0; i < j; i++) {
            int k = 2 * j - i;
            if (k < n) {
                if (s[i] != s[j] && s[j] != s[k] && s[k] != s[i]) {
                    res--;
                }
            }
        }
    }

    cout << res << endl;
}


Measured memory_bytes: 3580
import sys
import math
sys.setrecursionlimit(20000000)
input = sys.stdin.readline
x,y,z,p = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
a.sort()
b.sort()
c.sort()
"""
if x*y*z <= 3*10**6:
    abc = []
    for i in range(x):
        for j in range(y):
            for k in range(z):
                abc.append(a[i]+b[j]+c[k])
    abc.sort()
    abc = abc[::-1]
    for i in range(p):
        print(abc[i])  
    exit()
"""
ab = []
for i in range(x):
    for j in range(y):
        ab.append(a[i]+b[j])
ab.sort()
c = c[::-1]
ab = ab[::-1]
ab.append(-2**62)
ans = []
miru = [0]*z
for i in range(z):
    if i + 1 == z:
        d = -2**60
    else:
        d = c[i+1]+ab[0]
    for j in range(i+1):
        flag = 0
        while ab[miru[j]] + c[j] >= d and (len(ans)<= p or ab[miru[j]] + c[j] >= ans[0]):
             ans.append(ab[miru[j]] + c[j])
             miru[j]+=1
             flag = 1
        if flag and len(ans) <=p+1:
            ans.sort()
ans.sort()
ans = ans[::-1]
for i in range(p):
    print(ans[i])

Measured memory_bytes: 254860
N=int(input())
S=[input() for i in range(N)]
S=sorted(S)
cnt=1
max_cnt=1
ans=[S[0]]
for i in range(N-1):
    if S[i]==S[i+1]:
        cnt+=1
    else:
        cnt=1
    if cnt==max_cnt:
        ans.append(S[i+1])
    if cnt>max_cnt:
        max_cnt=cnt
        ans=[S[i+1]]
ans=sorted(ans)
for i in ans:
    print(i)

Measured memory_bytes: 21544
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <limits>
#include <numeric>
#include <type_traits>

using namespace std;

int main(){
    int N,T;
    int c[1005];
    int t[1005];
    int ans=1005;

    cin >> N >> T;
    for(int i = 0; i < N; i++){
        cin >> c[i];
        cin >> t[i];
        if(t[i] <= T){
            if(ans >= c[i]){
                ans = c[i];
            }
        }
    }
    if(ans > 1000){
        cout << "TLE" << endl;
    }else{
        cout << ans << endl;
    }
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		try (Scanner sc = new Scanner(System.in)) {
			int K = sc.nextInt();
			if (K % 2 == 0) {
				System.out.println(-1);
				return;
			}
			boolean[] bls = new boolean[K];
			int idx = 1;
			int sevenAmari = 7 % K;
			int tempAmari = 0;
			while (true) {
				tempAmari += sevenAmari;
				tempAmari %= K;
				if (tempAmari == 0) {
					break;
				}
				if (bls[tempAmari]) {
					System.out.println(-1);
					return;
				}
				bls[tempAmari] = true;
				idx++;
				sevenAmari *= 10;
				sevenAmari %= K;
			}
			System.out.println(idx);
		}
	}
}

Measured memory_bytes: 36768
import java.io.*;
import java.util.*;
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
Scanner scan=new Scanner(System.in);
//int a=scan.nextInt();

//int b=scan.nextInt();
String b=scan.next();
int rong=b.length();
StringBuffer sb = new StringBuffer(b);
String dst = sb.reverse().toString();
if(rong<=2) {System.out.println(b);}
else {System.out.println(""+dst);}
	}
}


Measured memory_bytes: 22740
import java.util.Scanner;

/**
 *
 * @author cs18097
 */
public class Main {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        Scanner sc = new Scanner(System.in);
        int min = sc.nextInt();
        int max = 0;
        for (int i = 0; i < 4; i++) {
            max = sc.nextInt();
        }
        int k = sc.nextInt();
        if (k < max - min) {
            System.out.print(":(");
        } else {
            System.out.print("Yay!");
        }

    }

}


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

using namespace std;

int main()
{
    int e=0,d=0;
    string s;
    cin>>s;
    for(int i=0;s[i]!='\0';i++){
        if( ((i+1)%2==0) && (s[i]=='L' || s[i]=='U' || s[i]=='D') )e++;
      	else if ( ((i+1)%2!=0) && (s[i]=='R' || s[i]=='U' || s[i]=='D') )e++;
      	else d++;
    }
    if(e && d==0)cout<< "Yes";
  	else cout<<"No";
    return 0;
}


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

int main(int argc, char const* argv[])
{
	int a, b, C;
	cin >> a >> b >> C;
	cout << setprecision(15);
	cout << 0.5 * (double)a * b * sin((double)C*M_PI/180.) << endl;
	cout << a + b + sqrt((double)a*a + (double)b*b-2*a*b*cos(C*M_PI/180.)) << endl;
	cout << (double)a * b * sin(C*M_PI/180.) / (double)a << endl;
	return 0;
}



Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxN = 1e3+7;
const int maxV = 90010;
//const int INF = 1e9+9;
//const ll INF = (1ll)<<60;
const int INF = 2e9+9;
const int MOD = 1e9+7;



int main()
{
	int a,p;
	scanf("%d%d",&a,&p);
	int sum = 3*a + p;
	int ans = sum/2;
	cout<<ans<<endl;
	
	return 0;
}

Measured memory_bytes: 256
/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define p 1000000007
int dp[3000][3000];

string common(int l,string &str1,string &str2)
{
    //cout<<"yahan tak bh aya hai"<<"\n";
    int i,j;
    i=j=0;
    string str;
    int k=0;
    //cout<<l<<"\n";
    while(l>0)
    {
        //cout<<str.length()<<"\n";
        if(str1[i]==str2[j])
        {
            str.push_back(str1[i]); // pb tu tabi hoga jab dono equal honge........
            i++;
            j++;
            l--;
        }
        else
        {
            int option1=dp[i+1][j];
            int option2=dp[i][j+1];
            if(option1>=option2)
            {
                i++;
            }
            else if(option2>option1)
            {
                j++;
            }
            
            
        }
    }
    //cout<<"loop ke bahar nhi aa paa rha hai"<<"\n";
    return str;
}
int  length(int i,int j,string &str1,string &str2)
{
    //cout<<"enter hua hai"<<"\n";
    if(i<str1.length() && j<str2.length())
    {
        if(dp[i][j]!=-1)
        {
            return dp[i][j];
        }
        
        if(str1[i]==str2[j])
        {
            return dp[i][j]=1+length(i+1,j+1,str1,str2);  // increment tabi hoga jab length samehogi...
            // 
        }
        else
        {
            int option1,option2;
            option1=length(i+1,j,str1,str2);
            option2=length(i,j+1,str1,str2);
            
            return dp[i][j]=max(option1,option2);
        }
    }
    else
    {
        return 0;
    }
}

string solve(string &str1,string &str2) // this function will return the common subsequence....
{
    memset(dp,-1,sizeof(dp)); 
    int l=length(0,0,str1,str2);  // it reprsents the length of the lcs...
    //cout<<l<<"\n";
    return common(l,str1,str2);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    string str1,str2;
    cin>>str1>>str2;
    
    cout<<solve(str1,str2);
    return 0;
}





Measured memory_bytes: 35840
import bisect,collections,copy,heapq,itertools,math,string
import sys
def S(): return sys.stdin.readline().rstrip()
def M(): return map(int,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
x, y, z = M()
ans= 0
for i in range(1, 50000):
    if y*i + z*(i+1) <= x:
        ans = i
    else:
        break
print(ans)

Measured memory_bytes: 74620
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<cstring>
#include<math.h>
#include<bitset>
#include<queue>
#include<set>
#include<iomanip>
#include<math.h>
#include<assert.h>
// #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr long long int INFLL = 1001001001001001LL;
constexpr int INFI = 1000000007;
const int mod = 1000000007;

int main(){
int n,k;
long long sum=0;
cin>>n>>k;
vector<int>h(n);
for(int i=0;i<n;i++){
    cin>>h.at(i);
}
sort(h.begin(),h.end());
for(int i=0;i<n-k;i++){
    sum+=h.at(i);
}
cout<<sum<<endl;
}









Measured memory_bytes: 1024
#include <iostream>
#include <iomanip>
#include <complex>
#include <vector>
#include <algorithm>
#include <cmath>
#include <array>
#include <limits>
using namespace std;
#define X real()
#define Y imag()
typedef complex<double> P;
typedef vector<P> VP;
const double EPS = 1e-8;
const double INF = 1e12;
const double NaN = std::numeric_limits<double>::quiet_NaN();
struct C{
    P p;
    double r;
    C(const P& p, const double& r) : p(p), r(r) {}
    C(){}
};

double cross(P a, P b){
    return (conj(a)*b).Y;
}
bool isParallel(const P &a, const P &b){
    return abs(cross(a,b)) < EPS;
}

P circum_center(const P &A, const P &B, const P &C){
    double a = norm(B - C);
    double b = norm(C - A);
    double c = norm(A - B);
    double denom = a*(b+c-a) + b*(c+a-b) + c*(a+b-c);
    if(denom < EPS) return P(NaN, NaN);
    return (a*(b+c-a)*A + b*(c+a-b)*B + c*(a+b-c)*C) / denom;
}

C minimum_enclosing_circle(const VP &p){
    vector<C> candidate;
    int n = p.size();
    for(int i=0; i<n; i++){
        for(int j=i+1; j<n; j++){
            for(int k=j+1; k<n; k++){
                if(isParallel(p[j]-p[i], p[k]-p[i])){
                    continue;
                }
                P cc = circum_center(p[i], p[j], p[k]);
                candidate.emplace_back(cc, abs(cc-p[i]));
            }
            P mid = (p[i] +p[j]) /2.0;
            candidate.emplace_back(mid, abs(mid-p[i]));
        }
    }
    C res;
    double rmin = INF;
    for(C c: candidate){
        bool ok = true;
        if(c.r > rmin) continue;
        for(P po: p){
            if(abs(c.p -po) > c.r +EPS){
                ok = false;
                break;
            }
        }
        if(ok){
            rmin = c.r;
            res = c;
        }
    }
    return res;
}

int main(){
    int n;
    cin >> n;
    VP p(n);
    for(int i=0; i<n; i++){
        double x,y;
        cin >> x >> y;
        p[i] = P(x, y);
    }
    C cc = minimum_enclosing_circle(p);
    cout << fixed << setprecision(10);
    cout << cc.r << endl;
    return 0;
}


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

string make(vector<int> p){
    string s = "";
    for ( int i = 0; i < n; i++){
      ostringstream oss;
      oss << p[i];
      s += oss.str();
    }
    return s;
}

int main(){
  cin >> n;
  vector<int> p(n), q(n);
  for ( int i = 0; i < n; i++){
    cin >> p[i];
  }
  for ( int i = 0; i < n; i++){
    cin >> q[i];
  }
  string ps = make(p);
  string qs = make(q);

  sort(p.begin(), p.end());
  vector<string> ss;
  do {
    string s = make(p);
    ss.push_back(s);
  } while (next_permutation(p.begin(), p.end()));
  sort(ss.begin(), ss.end());

  long long a, b = 0;
  for ( int i = 0; i < ss.size(); i++){
    if ( ss[i] == ps ){
      a = i;
    }
    if ( ss[i] == qs ){
      b = i;
    }
  }

  cout << abs(a-b) << endl;

  return 0;
}

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

int main(){
    int h,n,su=0,a;
    cin>>h>>n;
    for(int i=0;i<n;i++){
        cin>>a;
        su+=a;
    }
    if(su<h){
        cout<<"No"<<endl;
    }else{
        cout<<"Yes"<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long n,x,y,z,d,ma;
int main()
{

    scanf("%d%d%d%d%d",&x,&y,&z,&d,&n);
   

    cout<<min(min(min(4*x,2*y),z)*n,(n/2*d+n%2* min(min(4*x,2*y),z)))<<endl;

    return 0;
}

Measured memory_bytes: 256
/**
 *      ABC 73 B
 *      author  : kyomukyomupurin
 *      created : 2018-09-04 22:33:03
**/

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int N; cin >> N;
    int l[N + 1]; int r[N + 1];
    for (int i = 0; i < N; ++i) {
        cin >> l[i] >> r[i];
    }

    int sum = 0;
    for (int i = 0; i < N; ++i) {
        sum += r[i] - l[i] + 1;
    }

    cout << sum << endl;
    return 0;
}

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

int main()
{
	int N, M;
	cin >> N >> M;
	vector<vector<int>> G(N, vector<int>(N));
	for (int i = 0, a, b; i < M; i++) {
		cin >> a >> b;
		G[a - 1][b - 1]++;
		G[b - 1][a - 1]++;
	}
	long long res = 0;
	vector<int> g(N);
	for (int i = 0; i < N; i++) {
		g[i] = i;
	}
	do {
		bool f = true;
		for (int i = 1; i < N; i++) {
			if (G[g[i - 1]][g[i]] == 0) {
				f = false;
				break;
			}
		}
		if (f) {
			res++;
		}
	} while (next_permutation(g.begin() + 1, g.end()));
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 256
//nani?
#include<bits/stdc++.h>
#define pi acos(-1);
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define f(i,a,b) for( int i = a; i < b ; i++ )
#define sor(a) sort( a.begin(), a.end() )
#define rsor(a) sort( a.rbegin(), a.rend() )
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
//#define inf 1LL<<62
typedef long long ll;
typedef double ld;
using namespace std;
const ll inf=1e10+6;
const ll MOD=1e9+7;
const ll mod=998244353;
// ac cmtr;
const int MAX_N = 1e6+5;
const int LG = 25;

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

ll a[MAX_N];

int main(){
    fastio;
    ll n;
    cin>>n;
    ll cnt = 0;
    f(i,0,n) cin>>a[i];
    f(i,0,n){
        if(a[i] == (i+1)) cnt++;
    }
    if((n-cnt) <= 2) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;

}






Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n,m;
  cin >> n >> m;
  vector<int> vec(n+1);
  for(int i = 0;m>i;i++){
    int a,b;
    cin >> a >> b;
    vec.at(a-1)+= 1;
    vec.at(b-1)+= 1;
  }
  for(int i = 0;n>i;i++)
    cout << vec.at(i) << endl;
}

Measured memory_bytes: 256
#include<iostream>
#define lli long long int
using namespace std;
// Problem https://atcoder.jp/contests/abc048/tasks/abc048_b
// Reference https://atcoder.jp/contests/abc048/submissions/1014095
// C++ 2nd mission
lli solver(lli A,lli LARGEA,lli DEVIDE){
    lli result;
    result = 0;
    result = (LARGEA+DEVIDE) / DEVIDE - ( A - 1 + DEVIDE ) / DEVIDE; 
    return result;
}


int main(void){
    lli answer;
    answer = 0;
    lli a,b,x;
    cin >> a >> b >> x;
    answer=solver(a,b,x);
    cout << answer << endl;
    return 0;
}

Measured memory_bytes: 256
s = input()
s_reverse = s[::-1]

output = 'NO'

while(True):
    if (s_reverse[:5] == 'erase'[::-1] or s_reverse[0:5] == 'dream'[::-1]):
        s_reverse = s_reverse[5:]
    elif (s_reverse[:6] == 'eraser'[::-1]):
        s_reverse = s_reverse[6:]
    elif (s_reverse[:7] == 'dreamer'[::-1]):
        s_reverse = s_reverse[7:]
    else:
        if (len(s_reverse) == 0):
            output = 'YES'
        break
        
print(output)

Measured memory_bytes: 3316
import java.util.Scanner;
import java.util.StringJoiner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long y = sc.nextLong();
        for (int i = 0; i < n + 1; i++) {
            for (int j = 0; j < n - i + 1; j++) {
                if (y == 10000 * i + 5000 * j + 1000 * (n - i - j)) {
                    StringJoiner sj = new StringJoiner(" ");
                    sj.add(String.valueOf(i));
                    sj.add(String.valueOf(j));
                    sj.add(String.valueOf(n - i - j));
                    System.out.println(sj.toString());
                    return;
                }
            }
        }
        System.out.println("-1 -1 -1");
    }

}


Measured memory_bytes: 23764
/*

AさんとBさんは、それぞれ4教科のテストを受けた。
AさんとBさんのテストの点数を読み込み、合計点の高い方を出力せよ。

やり方：
	・Aさんの点数入力。
	・終わったらAさんの合計点を計算。
	・Bさんの点数入力。
	・終わったらBさんの合計点を計算。
	・大きい方を出力して終わり。





*/

#include <stdio.h>

int main()
{
	int a,b;
	int s=0,t=0;
	int i;
	for(i=0; i<4; i++){
		scanf("%d", &a);
		s+=a;
	}
	for(i=0; i<4; i++){
		scanf("%d", &b);
		t+=b;
	}
	if(s>t){
		printf("%d\n", s);
	}
	else if(t>s){
		printf("%d\n", t);
	}
	else{
		printf("%d\n", s);
	}
	return 0;
}

Measured memory_bytes: 592
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#include <algorithm>
#define rep(i,n) for(int i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
using namespace std;
using Graph = vector<vector<int>>;
typedef long long ll;
//using Graph = vector<vector<pair<ll,ll>>>;
const int mod =1e+9+7;

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

    vector<ll>a,p;
ll f(ll n,ll x){
        if(n==0)return 1;
        if(x==1)return 0;

    else if(x<=1+a[n-1])return f(n-1,x-1);
    else if(x==2+a[n-1])return p[n-1]+1;
    else if(x<=2+2*a[n-1])return p[n-1]+1+f(n-1,x-2-a[n-1]);
    else if(x==3+2*a[n-1])return 2*p[n-1]+1;
}
int main(){
    ll N,X; 
    cin>>N>>X;
    a.resize(N+1);
    p.resize(N+1);
    a[0]=1;
    p[0]=1;
    for(int i=1;i<=N;i++){
        a[i]=a[i-1]*2+3;
        p[i]=p[i-1]*2+1;
    }
    cout<<f(N,X)<<endl;
}











Measured memory_bytes: 3552
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>



using namespace std;
int n;
int p;
int member[50];
void solve(){
  int stone = p;
  long i = 0;
  while(true){
    //cout << "tarn" << i << "stone,0,1,2 ="<< stone <<"," <<member[0] << ","<< member[1]<< "," <<member[2] <<endl;

    if(stone == 1 && member[i%n] == p-1){
      cout << i%n << endl;
      member[i%n] = 0;
      break;
    }else if(stone > 0){
      member[i%n] ++;
      stone --;
      i++;
    }else{
      stone += member[i%n] ;
      member[i%n] = 0;
      i++;
    }
  }
}

int main(){

  while(true){
    cin >> n >> p;
    if(n == 0 && p == 0) break;
    solve();
  }

  return 0;
}



Measured memory_bytes: 3036
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<string>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
#include<iomanip>

#define REP(i,n) for(int i=0;i<(n);i++)
#define EPS (1e-7)
#define INF (2e9)
// cout << setprecision(10)

using namespace std;
typedef long long int ll;
const ll MOD = 1000000007;

int X, Y;
int main(void){
    cin >> X >> Y;
    bool f = true;
    for(int i=0;i<=X;i++){
        if(2*i + 4*(X-i) == Y) {
            cout << "Yes" << endl;
            f = false;
            break;
        }
    }
    if(f) cout << "No" << endl;
    return 0;
}



Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<LL,LL> P;
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; }
template<typename T> T gcd(T a,T b){return b?gcd(b,a%b):a;}
const LL mod=1000000007;
const LL LINF=1LL<<62;
const int INF=1<<30;
int dx[]={1,0,-1,0,-1,1,1,-1};
int dy[]={0,1,0,-1,-1,-1,1,1};


int main(){
    int n;cin >> n;
    string x;cin >> x;
    reverse(ALL(x));
    vector<LL> s(n, -1);
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if(x[i] - '0') cnt++;
    }
    if(cnt == 0){
        for (int i = 0; i < n; i++) {
            cout << 1 << endl;
        }
        return 0;
    }
    LL a=0,b=0;
    vector<LL> pa(n + 1, 1), pb(n + 1, 1);
    for (int i = 0; i < n; i++) {
        if(x[i] - '0'){
            a = (a + pa[i]) % (cnt + 1);
            if(cnt > 1) b = (b + pb[i]) % (cnt - 1);
        }
        pa[i + 1] = pa[i] * 2 % (cnt + 1);
        if(cnt > 1) pb[i + 1] = pb[i] * 2 % (cnt - 1);
    }
    for (int i = 0; i < n; i++) {
        if(x[i] - '0'){
            if(cnt > 1) s[i] = (b - pb[i] + (cnt - 1)) % (cnt - 1);
        }
        else{
            s[i] = (a + pa[i]) % (cnt + 1);
        }
    }
    reverse(ALL(x));
    reverse(ALL(s));
    for (int i = 0; i < n; i++) {
        if(s[i] == -1){
            cout << 0 << endl;
            continue;
        }
        int ans = 1;
        while(s[i]){
            int c = __builtin_popcount(s[i]);
            s[i] %= c;
            ans++;
        }
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 8348
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int K = s.nextInt();
        int gcd = 0;

        for (int i = 1; i <= K; i++) {
            for (int j = 1; j <= K; j++) {
                for (int k = 1; k <= K; k++) {
                    gcd += gcd(gcd(j, k), i);
                }
            }
        }

        System.out.println(gcd);
        s.close();
    }

    public static int gcd(int p, int q) {
        if (p % q == 0) {
            return q;
        }
        return gcd(q, p % q);
    }
}

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

#define ll long long
#define ull unsigned long long

using namespace std;

int main() {
	string s, t;
	cin >> s >> t;
	
	int n = s.size();
	map<char, int> m;
	map<char, string> mm;
	map<char, string> mmm;
	for (int ii = 0; ii < n; ++ii){
		if (s[ii] == t[ii]){
			m[s[ii]]++;
		}
		mm[s[ii]] += t[ii];
		mmm[t[ii]] += s[ii];
	}

	bool ans = true;
	for (char c = 'a'; c <= 'z'; ++c){
		if (mm[c].size() > 1){
			for (int ii = 1; ii < mm[c].size(); ++ii){
				if (mm[c][0] != mm[c][ii]){
					ans = false;
					cout << "No" << "\n";		
					return 0;
				}
			}
		}
		if (mmm[c].size() > 1){
			for (int ii = 1; ii < mmm[c].size(); ++ii){
				if (mmm[c][0] != mmm[c][ii]){
					ans = false;
					cout << "No" << "\n";		
					return 0;
				}
			}
		}
	}

	for (int ii = 0; ii < n; ++ii){
		if (s[ii] != t[ii]){
			if ( (m[s[ii]] > 0) || (m[t[ii]] > 0) ){
				ans = false;
				cout << "No" << "\n";		
				return 0;
			}
		}
	}

	cout << "Yes" << "\n";	

	return 0;
}


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

const int SIZE = 1E6;

int A[SIZE];
struct poss{
	int pos, T;
} P[SIZE], K[SIZE];

bool cmp(poss A, poss B) {
	return A.T > B.T;
}

int main() {
	int Tot; cin >> Tot;
	for(int pos = 1; pos <= Tot; pos++)
		cin >> A[pos];
	for(int pos = 1; pos <= Tot; pos += 2)
		P[A[pos]].T++, P[A[pos]].pos = A[pos];
	for(int pos = 2; pos <= Tot; pos += 2)
		K[A[pos]].T++, K[A[pos]].pos = A[pos];
	sort(P, P + SIZE - 1, cmp); sort(K, K + SIZE - 1, cmp);
	
	if(P[0].T == P[1].T || K[0].T == K[1].T) {
		cout << (Tot - P[0].T - K[0].T) << endl; return 0;
	}
	if(P[0].pos == K[0].pos) {
		if(P[1].T == 0)
			cout << Tot - P[0].T - K[1].T << endl;
		else if(K[1].T == 0)
			cout << Tot - P[1].T - K[0].T << endl;
		else 
			cout << min(Tot - P[1].T - K[0].T, Tot - P[0].T - K[1].T) << endl;
	}
	else 
		cout << (Tot - P[0].T - K[0].T) << endl;
}


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

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;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 SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)

#define INF 100000000
#define MOD 1000000007
#define writeln(n) cout<<n<<endl
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;
//vector<tuple<long long, long long, long long>>vec;

template<class T>
inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

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

const int inf=100000000;

llong pownew(llong m, llong n) {
        if (n == 0) { return 1; }
        if (n % 2 == 0) { return pow(m*m, n/2); }
        return pow(m, n-1) * m;
    }

bool isprime(int p) {
    if (p == 1) return false;
    for (int i = 2; i < p; i++) {
        if (p%i == 0) return false;
    }
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n; cin>>n;
    vector<llong> cnt(5,0);
    REP(i,n)
    {
        string s; cin>>s;
        if(s[0]=='M') ++cnt[0];
        else if(s[0]=='A') ++cnt[1];
        else if(s[0]=='R') ++cnt[2];
        else if(s[0]=='C') ++cnt[3];
        else if(s[0]=='H') ++cnt[4];
    }
    vector<vector<int>> comb{{0,1,2},{0,1,3},{0,1,4},{0,2,3},{0,2,4},{0,3,4},{1,2,3},{1,2,4},{1,3,4},{2,3,4}};
    llong ans=0;
    REP(i,comb.size())
    {
        ans+=cnt[comb[i][0]]*cnt[comb[i][1]]*cnt[comb[i][2]];
    }
    cout<<ans<<endl;
    return  0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <fstream>
#include <sstream>
#include <iomanip>

using namespace std;

long long MOD = 1000000007;

int main(){
    int X;
    cin >> X;
    int rest=X%100;

    int temp=rest/5;
    int tmp=rest%5;

    int ans=temp*105;
    if(tmp!=0){
        ans+=100+tmp;
    }
    if(ans>X){
        cout << '0' << endl;
    }else{
        cout << '1' << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
#define xx         first
#define yy         second
#define pb         push_back
#define mp         make_pair
#define LL         long long
#define inf        INT_MAX/3
#define mod        1000000007ll
#define PI         acos(-1.0)
#define linf       (1ll<<60)-1
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define REP(I,N)   FOR(I,0,N)
#define For(I,N)   for(int I=1;I<=(N);I++)
#define ALL(A)     ((A).begin(), (A).end())
#define set0(ar)   memset(ar,0,sizeof ar)
#define vsort(v)   sort(v.begin(),v.end())
#define setinf(ar) memset(ar,126,sizeof ar)
#define SZ(X) ((int)(X.size()))
#define LG(X) ((int)(X.length()))
#define CL(X) (X).clear()
#define MAXEL(A,B) (*max_element(A,B))
#define MINEL(A,B) (*min_element(A,B))
#define ROPEN(X) freopen(X,"r",stdin)
#define WOPEN(X) freopen(X,"w",stdout)
#define BG(X) (X.begin())
#define EN(X) (X.end())
#define VI vector<int>
#define PII pair<int,int>
 
//cout << fixed << setprecision(20) << p << endl;
 
template <class T> inline T bigmod(T p,T e,T M){
    LL ret = 1;
    for(; e > 0; e >>= 1){
        if(e & 1) ret = (ret * p) % M;
        p = (p * p) % M;
    } return (T)ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}


int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int x1,y1,x2,y2;
	cin>>x1>>y1>>x2>>y2;
	cout<<x2-y2+y1<<" "<<y2+x2-x1<<" "<<x1-y2+y1<<" "<<y1+x2-x1<<endl;
	return 0;
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"io"
	"log"
	"os"

	"strconv"
)

func solve(in io.Reader, out io.Writer) error {
	sc := bufio.NewScanner(in)
	sc.Split(bufio.ScanWords)

	a, b := nextInt(sc), nextInt(sc)

	var c int = 0

	for i := a; i <= b; i++ {
		s := strconv.Itoa(i)
		if s[0] == s[4] && s[1] == s[3] {
			c++
		}
	}

	fmt.Fprintln(out, c)
	return nil
}

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

func main() {
	err := solve(os.Stdin, os.Stdout)
	if err != nil {
		log.Fatal(err)
	}
}


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

typedef long double ld;
typedef unsigned long ul;
typedef long long ll;
typedef unsigned long long ull;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<long> vl;
typedef vector<double> vd;
typedef map<int,int> mii;
typedef pair<int,int> pii;
typedef pair<long,long> pll;

#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,a,n) for(int i=a;i<n;i++)
#define ALL(a) (a).begin(),(a).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))

#define pi 3.14159265358979
#define eps 1e-9
#define inf 1<<30
#define MOD 1000000007 // 1e9+7

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

  long A;
  ll sum = 0;
  map<ll, long> mp;
  for(long i=0; i<N; i++){
    cin >> A;
    sum += A;
    if( mp.count(sum) == 0 ){
      mp[sum] = 1;
    } else {
      mp[sum] += 1;
    }
  }

  ll ret = 0;
  for( auto x : mp ){
    if( x.first == 0 ) ret += x.second;
    ret += x.second * (x.second - 1) / 2;
  }

  cout << ret << endl;

  return 0;
}



Measured memory_bytes: 12800
#include<stdio.h>
int main(void)
{
	int a,b,c,d;
	scanf("%d %d %d %d",&a,&b,&c,&d);
	if(a==b&&c==d){
		printf("yes\n");
	}
	else if(a==c&&b==d){
		printf("yes\n");
	}
	else if(a==d&&b==c){
		printf("yes\n");
	}
	else if(a==b==c==d){
		printf("yes\n");
	}
	else {
		printf("no\n");
	}
	
	return 0;
}


Measured memory_bytes: 2604
(let* ((n (parse-integer (read-line)))
       (strs (loop :for i :from 1 :to n
                  :collect (read-line)))
       (char-count (make-array 26 :initial-element 0)))
  (loop :for c :across (car strs)
        :do (incf (aref char-count (- (char-code c) (char-code #\a)))))
  (loop 
        :for s :in strs
        :for char-count-s = (make-array 26 :initial-element 0)
        :do (progn
              (loop :for c :across s
                    :do (incf (aref char-count-s (- (char-code c) (char-code #\a)))))
              (loop :for i :from 0 :below 26
                    :do (when (< (aref char-count-s i) (aref char-count i))
                        (setf (aref char-count i) (aref char-count-s i))))))
  (loop :for count :across char-count
        :for i :from 0 :below 26
        :for char = (code-char (+ i (char-code #\a)))
        :do (dotimes (j count)
              (format t "~c" char)))
  (format t "~%"))


Measured memory_bytes: 19812
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		String[] data;
		
		Scanner scanner = new Scanner(System.in);
		
	
		while(scanner.hasNext()) {
			data = scanner.nextLine().split(" ");
			int dataInt = Integer.parseInt(data[0]) + Integer.parseInt(data[1]);
			System.out.println(String.valueOf(dataInt).length());
		}
		
		scanner.close();
		
	}

}

Measured memory_bytes: 26092
#include<iostream>
using namespace std;
long N,X,M;
int vis[1<<17];
long pre[1<<17];
main()
{
	cin>>N>>X>>M;
	for(int i=0;i<M;i++)vis[i]=-1;
	long ans=0;
	int tu=0;
	while(N>0)
	{
		N--;
		vis[X]=tu++;
		pre[X]=ans;
		ans+=X;
		X=X*X%M;
		if(vis[X]>=0)
		{
			int be=tu-vis[X];
			ans+=(ans-pre[X])*(N/be);
			N%=be;
		}
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 4744
#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
#include <map>
#include <set>
#include <string>
#include <iostream>
#include <cassert>
#include <cmath>
#include <cstdlib>
#include <cstring>
using namespace std;

int main() {
        int n;
        scanf("%d", &n);
        map<string, int> red, blue;
        for (int i = 0; i < n; i ++) {
                string s;
                cin >> s;
                red[s] ++;
        }
        scanf("%d", &n);
        for (int i = 0; i < n; i ++) {
                string s;
                cin >> s;
                blue[s] ++;
        }
        int ans = 0;
        for (auto it : red) {
                ans = max(ans, it.second - blue[it.first]);
        }
        printf("%d\n", ans);
        return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define PI 3.14159265358979323846
#define MAXINF (1e18L)
#define INF (1e9L)
#define EPS (1e-9)
#define MOD ((ll)(1e9+7))
#define REP(i, n) for(int i=0;i<int(n);++i)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define ALL(v) v.begin(),v.end()
#define FIND(v,x) (binary_search(ALL(v),(x)))
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v));reverse(ALL(v))
#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
#define Yes(n) cout<<((n)?"Yes":"No")<<endl
#define YES(n) cout<<((n)?"YES":"NO")<<endl
#define pb push_back
#define fi first
#define se second
using namespace std;
template<class A>void pr(A a){cout << (a) << endl;}
template<class A,class B>void pr(A a,B b){cout << a << " "  ;pr(b);}
template<class A,class B,class C>void pr(A a,B b,C c){cout << a << " " ;pr(b,c);}
template<class A,class B,class C,class D>void pr(A a,B b,C c,D d){cout << a << " " ;pr(b,c,d);}
template<class T> void pr_vec(vector<T> &v, char ep=' '){int n=v.size();REP(ni,n){cout<<v[ni];if(ni!=n-1)cout<<ep;}cout<<endl;};
template<class T> inline bool chmin(T& a, T b){return a>b ? a=b, true : false;}
template<class T> inline bool chmax(T& a, T b){return a<b ? a=b, true : false;}
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll,ll> pll;

int main(void)
{
    int N;
    cin >> N;
    vector<string> S(N);
    REP(i, N) cin >> S[i];
    vector<vector<int>> c(N);
    REP(i, N)REP(j, N) if(S[i][j]=='1') c[i].pb(j);

    int ans = -100;
    REP(i, N){
        int tmp = [&](){
            vector<int> ok(N, -10);
            queue<int> q; q.push(i);
            ok[i] = 1;
            while(!q.empty()){
                auto f = q.front(); q.pop();
                for(auto&& ci : c[f]){
                    if(ok[ci]==-10){
                        ok[ci] = ok[f]+1;
                        q.push(ci);
                    }else if(ok[ci]!=ok[f]-1&&ok[ci]!=ok[f]+1){
                        return -1;
                    }
                }
            }
            return *(max_element(ALL(ok)));
        }();
        chmax(ans, tmp);
    }
    pr(ans);
}

Measured memory_bytes: 3876
#include<stdio.h>
int main()
{
    char n[4];
    scanf("%s", n);
    int i;
    for (i = 0; i < 3; i++)
        if (n[i] == '1')
            n[i] = '9';
        else
            n[i] = '1';
    printf("%s\n", n);
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){

    int t; //first line

    scanf("%d",&t);

    int r[t];
    int i = 0;
    int j;
    int p;


    while(i < t){
        scanf("%d",&r[i]);
        i++;
    }

    i = 0;
    p = r[1] - r[0];
    int minr = r[0];

    for(j=1; j<t; j++){
        
        if(minr > r[j-1]){
            minr = r[j-1];
        }
        
        if(p < (r[j] - minr)){
            p = r[j] - minr;
        }
    }


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

    return 0;

}


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

int main(){
    int a[3],K;
    cin>>a[0]>>a[1]>>a[2]>>K;
    sort(a,a+3);
    REP(i,K){
        a[2]*=2;
    }
    cout<<a[0]+a[1]+a[2]<<endl;
}

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

int main()
{
  string number;
  cin >> number;
  int size = (1 << (number.size() - 1)) - 1;
  long int total = 0;

  for (int i = 0; i <= size; ++i)
  {
    int psp = 0;
    int sp = 0;

    for (int b = 0; b < number.size(); ++b)
    {
      if (i & (1 << b))
      {
        psp = sp;
        sp = b + 1;
        auto ss = number.substr(psp, sp - psp);
        //cout << ss << endl;
        total += stol(ss);
      }
    }
    if (sp < number.size())
    {
      //cout << number.substr(sp) << endl;
      total += stol(number.substr(sp));
    }
  }

  cout << total << endl;

  return 0;
}

Measured memory_bytes: 256
// https://atcoder.jp/contests/abc166/tasks/abc166_b

#include <bits/stdc++.h>
using namespace std;

#define REP(i,n)   for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for(int i=(b); i<=(int)(e); i++)
#define DEBUG 1
#if DEBUG
  #define _GLIBCXX_DEBUG
  #define DUMP(a) REP(_i, a.size()) cout << a[_i] << (_i + 1 == a.size() ? "\n" : " ")
  #define DUMP2D(b) REP(_j, b.size()) DUMP(b[_j]); cout << endl
#else
  #define DUMP(a)
  #define DUMP2D(b)
#endif

const int N_MAX = 100;
const int K_MAX = 100;

int N, K;
vector<int> d;
vector<vector<int>> A;

vector<int> c;

int main() {
  cin >> N >> K;
  d = vector<int>(K);
  A = vector<vector<int>>(K);
  REP(i, K) {
    cin >> d[i];
    A[i] = vector<int>(d[i]);
    REP(j, d[i]) cin >> A[i][j];
  }

  c = vector<int>(N, 0);
  REP(i, K) REP(j, d[i]) c[A[i][j] - 1]++;

  int ans = 0;
  REP(i, N) if (c[i] == 0) ans++;
  cout << ans << endl;
}


Measured memory_bytes: 3624
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define ll long long int
#define mem(x) memset(x,0,sizeof(x))
#define setbits(x)  __builtin_popcount(x)
#define ull unsigned long long int
#define all(c) (c).begin(),(c).end()
#define debug(x) cout<<#x<<" :: "<<x<<endl;
#define debug2(x,y) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<endl;
#define cps CLOCKS_PER_SEC
#define complex cerr << "Time (in ms): " << (double)(clock() - clk) * 1000.0 / cps << '\n';
#define db double
#define endl "\n"
#define  fbo(x) find_by_order(x)
#define  ook(x) order_of_key(x)

using namespace __gnu_pbds;
using namespace std;

typedef tree<int, null_type, less<int>, rb_tree_tag,
            tree_order_statistics_node_update>
    os1;
typedef tree<int, null_type, greater<int>, rb_tree_tag,
            tree_order_statistics_node_update>
    os2;
typedef vector< int > vi;
typedef vector< vi > vvi;
typedef pair<ll,ll > ii;
typedef pair<ll,int> li;
inline void fast()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
}
const ll pi=31;
const ll MOD[2] = {1187278649, 1149736019};//for double hashing
const ll mod=(ll)(998244353);
ll pmod(ll x,ll n){
  ll r=1;
  while(n)
  {
    if(n&1LL)
      r=(r*x)%mod;
    x=(x*x)%mod;
    n=n/2;
  }
  return r;
}

//think recursively also
ll n,m,k;
ll fac[200005];
ll inv[200005];
void pre()
{  fac[0]=inv[0]=1;
  for(ll i=1;i<=200000;i++)
  {
    fac[i]=(fac[i-1]*i)%mod;
    inv[i]=pmod(fac[i],mod-2);
  }
}
ll C(ll n,ll r)
{
  ll ans=((fac[n]*inv[r])%mod*inv[n-r])%mod;
  ans=ans%mod;
  return ans;
}
void solve()
{   
  

  pre();
  cin>>n>>m>>k;
  //k+=1;
  ll ans=0;
  for(int i=0;i<=k;i++)
  { 

    ll a=(m*(pmod(m-1,n-i-1)))%mod;
    
    
      a=a*C(n-1,i);
      a=a%mod;
    
   ans+=a;
   ans%=mod;


  }
  cout<<ans<<endl;


  
}
int main()
{
   fast();
  
   // int t;
   // cin>>t;
   // for(int casee=1;casee<=t;casee++)
  {// cout<<"Case #"<<casee<<": ";
    solve();
  }
 
 
 
}


Measured memory_bytes: 6776
#define _USE_MATH_DEFINES
#pragma region include

#include <iostream>
#include <iomanip>
#include <stdio.h>

#include <sstream>
#include <algorithm>
#include <iterator>
#include <cmath>
#include <complex>

#include <string>
#include <cstring>
#include <vector>
#include <bitset>

#include <queue>
#include <set>
#include <map>
#include <stack>
#include <list>

#include <ctime>
////
//#include <random>//
#pragma endregion //#include
/////////

#pragma region typedef
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
#pragma endregion //typedef
////定数
const int INF = (int)1e9 + 10;
const LL MOD = (LL)1e9 + 7;
const LL LINF = (LL)4e18 + 20;
const LD PI = acos(-1.0);
const double EPS = 1e-9; 
/////////
using namespace::std;
//////////////

void solve() {
	vector<int> A(3);
	for (int i = 0; i < 3; ++i) {
		cin >> A[i];
	}
	sort(A.begin(), A.end());
	int ans = A[2] * 10 + A[0] + A[1];
	cout << ans << endl;
}

#pragma region main
signed main(void) {
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	std::cout << std::fixed;//小数を10進数表示
	cout << setprecision(16);//小数点以下の桁数を指定//coutとcerrで別	

	solve();
}
#pragma endregion //main()


Measured memory_bytes: 256
import sys
input = sys.stdin.readline

K = int(input())

A = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

print(A[K - 1])

Measured memory_bytes: 38384
#include<stdio.h>
int main(){
    int m,n,i,j,k,p;
    //scanf("%d",&m);
    for(i=1;i<=9;i++){
        //scanf("%d%d",&n,&k);
        for(j=1;j<=9;j++){
                if(i*j==90)break;
            printf("%dx%d=%d\n",i,j,i*j);
            }

        }
    return 0;
}



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

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

			String in = br.readLine();
			String chr[] = in.split(" ");
			int a = Integer.parseInt(chr[0]);
			int b = Integer.parseInt(chr[1]);
			int c = Integer.parseInt(chr[2]);
			 System.out.println(a*b*c/2/Math.max(a, Math.max(b, c)));
		}
	}
}

Measured memory_bytes: 25364
#include<iostream>
using namespace std;
int main()
{
	int x,y,a[5]={0},m=0,i;
	for(i=0;i<3;i++)
	{
		cin>>x>>y;
		a[x]++;
		a[y]++;
	}
	for(i=1;i<=4;i++)
	{
		if(a[i]>0&&a[i]<=2)
		{
			m++;
		}
	}
	if(m==4)
	{
		cout<<"YES"<<endl;
	}
	else
	{
		cout<<"NO"<<endl;
	}
	return 0;
} 

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <algorithm>
#include <iomanip>
#include <string.h>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define ALL(a)  (a).begin(),(a).end()

typedef long long lint;

using namespace std;

int main(){
  int N;
  cin>>N;
  vector<int> v[N];
  REP(i,N-1){
    int a,b;
    cin>>a>>b;
    a--;b--;
    v[a].push_back(b);
    v[b].push_back(a);
  }
  int c[N];
  REP(i,N)cin>>c[i];
  sort(c,c+N);
  lint M=0;
  REP(i,N-1)M+=c[i];
  queue<int> q;
  q.push(0);
  int d[N];
  REP(i,N)d[i]=-1;
  d[0]=0;
  while(!q.empty()){
    int p=q.front();
    q.pop();
    for(auto e:v[p])if(d[e]<0){
      q.push(e);
      d[e]=d[p]+1;
    }
  }
  vector<pair<int,int> > k;
  REP(i,N)k.push_back(make_pair(d[i],i));
  sort(ALL(k));
  reverse(ALL(k));
  int ans[N];
  REP(i,N){
    ans[k[i].second]=c[i];
  }
  cout<<M<<endl;
  REP(i,N)cout<<ans[i]<<" ";
  cout<<endl;
  return 0;
}


Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
 
#define rep(i,n) for(int i = 0;i<n;i++)
const long long MOD = 1000000007;

int main(){
  int n;cin >> n;
  vector<int> a(n);
  rep(i,n) cin >> a[i];
  int ans = 0;
  sort(a.begin(), a.end());
  for(int i = 0; i<n; i++){
    for(int j = i+1; j<n; j++){
      int r = lower_bound(a.begin(), a.end(), a[i]+a[j] ) - a.begin();
      int l = j+1;
      ans += r-l;
    }
  }
  cout << ans << "\n";
}

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

int main(){
 int n,ans=0;
 cin>>n;
 int l[2*n];
 for(int i=0;i<2*n;i++) cin>>l[i];
 sort(l,l+2*n);
 for(int i=0;i<2*n;i+=2)
 { ans+=l[i]; }
 cout<<ans;
 return 0;
}


Measured memory_bytes: 256
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""

n = onem()

dp = [0 for i in range(20000+1)]

for i in range(1,200+1):
	for j in range(1,200+1):
		for k in range(1,200+1):
			po = (i+j)**2 + (j+k)**2 + (k+i)**2
			if po <= 20000:
				dp[po] += 1

for i in range(2,2*n+1,2):
	print(dp[i])

Measured memory_bytes: 69472