akhauriyash/Code-Regression huggingface dataset:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
from math import floor, sqrt, factorial, hypot, log  # log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter, defaultdict, deque
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint


def ceil(a, b): return (a + b - 1) // b


inf = float('inf')
mod = 10 ** 9 + 7


def pprint(*A):
    for a in A:     print(*a, sep='\n')


def INT_(n): return int(n) - 1


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


def MF(): return map(float, input().split())


def MI_(): return map(INT_, input().split())


def LI(): return list(MI())


def LI_(): return [int(x) - 1 for x in input().split()]


def LF(): return list(MF())


def LIN(n: int): return [I() for _ in range(n)]


def LLIN(n: int): return [LI() for _ in range(n)]


def LLIN_(n: int): return [LI_() for _ in range(n)]


def LLI(): return [list(map(int, l.split())) for l in input()]


def I(): return int(input())


def F(): return float(input())


def ST(): return input().replace('\n', '')


def main():
    N = I()
    AC = 0
    WA = 0
    TLE = 0
    RE = 0
    for _ in range(N):
        S = ST()
        if S == "AC":
            AC += 1
        elif S == "WA":
            WA += 1
        elif S == "TLE":
            TLE += 1
        else:
            RE += 1
    print("AC x", AC)
    print("WA x", WA)
    print("TLE x", TLE)
    print("RE x", RE)


if __name__ == '__main__':
    main()


Measured memory_bytes: 84200
package main

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

var sc, wr = bufio.NewScanner(os.Stdin), bufio.NewWriter(os.Stdout)

func scanString() string   { sc.Scan(); return sc.Text() }
func scanRunes() []rune    { return []rune(scanString()) }
func scanInt() int         { a, _ := strconv.Atoi(scanString()); return a }
func scanInt64() int64     { a, _ := strconv.ParseInt(scanString(), 10, 64); return a }
func scanFloat64() float64 { a, _ := strconv.ParseFloat(scanString(), 64); return a }

func scanInts(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = scanInt()
	}
	return res
}

func debug(a ...interface{}) { fmt.Fprintln(os.Stderr, a...) }

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

//•*¨*•.¸¸♪main•*¨*•.¸¸♪(　-ω-)ノ　(　・ω・)
func main() {
	defer wr.Flush()
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 10000), 1001001)

	n := scanInt()
	a := scanInts(n)

	dp := make([][]int, n+1)
	for i := 0; i < n+1; i++ {
		dp[i] = make([]int, n+1)
	}

	b := make([]pair, n)
	for i := 0; i < n; i++ {
		b[i] = pair{i, a[i]}
	}

	sort.Slice(b, func(i, j int) bool {
		return b[i].num > b[j].num
	})

	debug(b)

	ans := 0
	var dfs func(l, r int)
	dfs = func(l, r int) {
		if l+r == n {
			ans = max(ans, dp[l][r])
			return
		}

		dp[l+1][r] = max(dp[l+1][r], dp[l][r]+b[l+r].num*(b[l+r].x-l))
		dp[l][r+1] = max(dp[l+1][r], dp[l][r]+b[l+r].num*(b[l+r].x-(n-1-r)))

		dfs(l+1, r)
		dfs(l, r+1)
	}

	for i := 0; i < n; i++ {
		for j := 0; j <= i; j++ {
			dp[j+1][i-j] = max(dp[j+1][i-j], dp[j][i-j] + b[i].num*abs(b[i].x-j))
			dp[j][i-j+1] = max(dp[j][i-j+1], dp[j][i-j] + b[i].num*abs(b[i].x-(n-1-(i-j))))
			if i == n-1 {
				ans = max(ans, dp[j+1][i-j])
				ans = max(ans, dp[j][i-j+1])
			}
		}
	}

	fmt.Fprintln(wr, ans)

}

type pair struct {
	x, num int
}


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

int main(void){

  int N = 0;
  scanf("%d\n",&N);
  int inputData[100000] = {};
  int countData[100000] = {};
  int resultData[100000] = {};


  for(int i = 0;i < N;i++){
    scanf("%d\n",&inputData[i]);
    countData[i] = i+1;
  }

  for(int i = 0;i < N;i++){
    resultData[inputData[i]] = countData[i];
  }

  for(int i = 0;i < N;i++){
    printf("%d ",resultData[i+1]);
  }
  printf("\n");

}


Measured memory_bytes: 1920
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <numeric>
#include <limits>


struct Point
{
	int h, w, depth;
};

void copy_maze(int src[22][22], int dest[22][22], int H, int W)
{
	for (int h = 0; h <= H + 1; h++)
	{
		for (int w = 0; w <= W + 1; w++)
		{
			dest[h][w] = src[h][w];
		}
	}
}

int max_path_from(int maze[22][22], int H, int W, int start_h, int start_w)
{
	int z[22][22];
	copy_maze(maze, z, H, W);

	int max_depth = 0;
	std::queue<Point> queue;
	z[start_h][start_w] = 0;
	queue.push(Point{ start_h, start_w, 0 });
	while (queue.size() > 0)
	{
		Point p = queue.front();
		max_depth = std::max(max_depth, p.depth);
		
		if (z[p.h - 1][p.w] == -1)
		{
			z[p.h - 1][p.w] = p.depth + 1;
			queue.push(Point{ p.h - 1, p.w, p.depth + 1 });
		}
		if (z[p.h + 1][p.w] == -1)
		{
			z[p.h + 1][p.w] = p.depth + 1;
			queue.push(Point{ p.h + 1, p.w, p.depth + 1 });
		}
		if (z[p.h][p.w - 1] == -1)
		{
			z[p.h][p.w - 1] = p.depth + 1;
			queue.push(Point{ p.h, p.w - 1, p.depth + 1 });
		}
		if (z[p.h][p.w + 1] == -1)
		{
			z[p.h][p.w + 1] = p.depth + 1;
			queue.push(Point{ p.h, p.w + 1, p.depth + 1 });
		}

		queue.pop();
	}

	return max_depth;
}

int search_max_path(int maze[22][22], int H, int W)
{
	int max_path = -1;
	for (int h = 1; h <= H; h++)
	{
		for (int w = 1; w <= W; w++)
		{
			if (maze[h][w] == -1)
			{
				int path = max_path_from(maze, H, W, h, w);
				max_path = std::max(max_path, path);
			}
		}
	}
	return max_path;
}

int main()
{
	int H, W;
	std::cin >> H >> W;

	int maze[22][22];
	// outside wall
	for (int h = 0; h <= H + 1; h++)
	{
		maze[h][0] = -10;
		maze[h][W+1] = -10;
	}
	for (int w = 0; w <= W + 1; w++)
	{
		maze[0][w] = -10;
		maze[H+1][w] = -10;
	}

	// inside
	for (int h = 1; h <= H; h++)
	{
		for (int w = 1; w <= W; w++)
		{
			char c;
			std::cin >> c;
			maze[h][w] = (c == '#') ? -10 : -1;
		}
	}

	std::cout << search_max_path(maze, H, W);
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main(void){
    int n, li[256], ans=1e-9;
    cin >> n;
    for(int i=0;i<n;i++) cin >> li[i];
    
    for(int i=0;i<n;i++) ans += li[i]; 
    
    for(int i=0;i<n;i++){
        int x=0,y=0;
        for(int j=0;j<i;j++){//i番目まで
            x += li[j];
        }
        for(int j=i;j<n;j++){//i番目以降
			y += li[j];
        }
    ans = min(ans, abs(x-y));
    }
    cout << ans << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define lli long long int
#define ulli unsigned long long int
#define ld long double
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define loop(i,a,b) for(lli i=a;i<b;i++)
#define initialize(array,size,value) for(lli i=0;i<size;i++) array[i]=value
#define couta(array,size) for(lli i=0;i<size;i++) cout<<array[i]<<" "
#define vl vector<lli>
#define vp vector< pair <lli,lli> >
#define sl set<lli>
#define msp multiset < pair < long long , long long > > S;
#define pll pair<lli, lli>
#define mll map<lli, lli>            //for( map<lli, lli>::iterator i=temp.begin();i!=temp.end();i++)cout<<i->fi<<" "<<i->se<<endl;
#define mvl map<lli, vl>
#define umll unordered_map<lli, lli>
#define vt vector<pair<lli, pll >  >
#define vf vector<pair<pll,pll > >
#define qu queue<lli>
#define pq priority_queue<lli>
#define dq deque <lli>
#define ptr vector<lli>::iterator
#define bs(array,x) binary_search(array.begin(),array.end(),x) // also valid for set and multiset
#define lb(array,x) lower_bound(array.begin(),array.end(),x)
#define ub(array,x) upper_bound(array.begin(),array.end(),x)
#define nobw(array,i,j) upper_bound(array.begin(), array.end(), j)-lower_bound(array.begin(), array.end(), i) //number of numbers between i & j
#define vc clear()
#define endl '\n'
#define sp system("pause");
#define INF 9223372036854775807
#define MINF -9223372036854775808
typedef tree<pll,null_type,less<pll>,rb_tree_tag,
tree_order_statistics_node_update> indexed_set;
//string binary = bitset<32>(n).to_string();  
lli mod=1000000007;
int main()
{
 	ios::sync_with_stdio(0);
    cin.tie(0);
    lli n,m;
    cin>>n>>m;
    vl adj[n+1];
    while(m--){
    	lli a,b;
    	cin>>a>>b;
    	adj[a].pb(b);
    }
    queue<pll> q;
    lli s,t;
    cin>>s>>t;
    q.push(mp(s,0));
    lli a[n+1][3];
    for(lli i=0;i<n+1;i++)for(lli j=0;j<3;j++)a[i][j]=INF;
    a[s][0]=0;
    while(!q.empty()){
    	lli v=q.front().fi,d=q.front().se;
    	q.pop();
    	for(auto u:adj[v]){
    		lli dis=(d+1)%3;
    		if(a[u][dis]!=INF)continue;
    		a[u][dis]=a[v][d]+1;
    		q.push(mp(u,dis));
    	}

    }
    if(a[t][0]==INF)cout<<-1;
    else cout<<a[t][0]/3;


    return 0;
} 

Measured memory_bytes: 8064
fn main() {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).expect("Fail");
    let vec: Vec<&str> = line.split_whitespace().collect();
    let a: f64 = vec[0].parse().unwrap();
    let b: f64 = vec[1].parse().unwrap();
    let x: f64 = vec[2].parse().unwrap();

    if a * a * b / 2_f64 >= x {
        println!(
            "{}",
            90_f64 - ((2_f64 * x / (a * b * b)).atan() * 180_f64 / std::f64::consts::PI)
        );
    } else {
        println!(
            "{}",
            (2_f64 * (a * a * b - x) / (a * a * a)).atan() * 180_f64 / std::f64::consts::PI
        );
    }
}


Measured memory_bytes: 4476
#!/usr/bin/python3
# -*- coding: utf-8 -*-


MOD = 1000000007


L = str(input())
dp_known = 0
dp_unknown = 1

for l in L:
  if l=="0":
    dp_known = (dp_known*3) % MOD
  else:
    dp_known = (dp_known*3+dp_unknown) % MOD
    dp_unknown = (dp_unknown*2) % MOD
print((dp_known+dp_unknown) % MOD)

Measured memory_bytes: 3188
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define SWAP(a, b) (a += b, b = a - b, a -= b)

int parent(int i)
{
    return (int)(i / 2);
}

int left(int i)
{
    return 2 * i;
}

int right(int i)
{
    return 2 * i + 1;
}

void upHeap(int *H, int i)
{
    while (parent(i) >= 1 && H[i] > H[parent(i)])
    {
        SWAP(H[i], H[parent(i)]);
        i = parent(i);
    }
}

void insert(int *H, int *hsize, int key)
{
    *hsize += 1;
    H[*hsize] = key;
    upHeap(H, *hsize);
}

void maxHeapify(int *H, int *hsize, int i)
{
    int u = i;
    int l = left(u);
    int r = right(u);
    int largest;

    if (l <= *hsize && H[l] > H[u])
    {
        largest = l;
    }
    else
    {
        largest = u;
    }
    if (r <= *hsize && H[r] > H[largest])
    {
        largest = r;
    }

    if (largest != u)
    {
        SWAP(H[u], H[largest]);
        maxHeapify(H, hsize, largest);
    }
}

int extractMax(int *H, int *hsize)
{
    int max = H[1];
    H[1] = H[*hsize];
    *hsize -= 1;

    maxHeapify(H, hsize, 1);

    return max;
}

int main(void)
{
    int H[2000001];
    char command[10];
    int hsize = 0;
    int key;
    int max_value;

    while (1)
    {
        scanf("%s", command);
        if (command[0] == 'e' && command[1] == 'n')
        {
            break;
        }
        else if (command[0] == 'i')
        {
            scanf("%d", &key);
            insert(H, &hsize, key);
        }
        else if (command[0] == 'e')
        {
            max_value = extractMax(H, &hsize);
            printf("%d\n", max_value);
        }
    }

    return 0;
}


Measured memory_bytes: 5648
import java.util.Scanner;

class Main{
        public static void main(String[] args){
                Scanner scn=new Scanner(System.in);
                int max=0;
                int value=0;
                int a=0;
                int b=0;
                int N=scn.nextInt();
                for(int i=0;i<N;i++){
                        a=scn.nextInt();
                        b=scn.nextInt();
                        if(max<a){
                                max=a;
                                value=b;
                        }
                }
                System.out.println(max+value);
        }
}

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

using namespace std;

int main()
{
    int m;
    
    scanf("%d", &m);
    
    while (m--){
        set<string> s;
        string st;
        char tmp[128];
        
        scanf("%s", tmp);
        
        st = (string)tmp;
        
        for (int i = 0; i < st.size() - 1; i++){
            string u = st.substr(0, i + 1), v = st.substr(i + 1, st.size() - i - 1);
            string ur = u, vr = v;
            reverse(ur.begin(), ur.end()); reverse(vr.begin(), vr.end());
            s.insert(u + v); s.insert(v + u);
            s.insert(u + vr); s.insert(vr + u);
            s.insert(ur + v); s.insert(v + ur);
            s.insert(ur + vr); s.insert(vr + ur);
        }
        
        printf("%d\n", s.size());
    }
    
    return (0);
}

Measured memory_bytes: 1316
//#define _GLIBCXX_DEBUG

#include<bits/stdc++.h>
#define PI 3.14159265359
using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
const int INF= 1e9+5;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll> >vvl;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> T;
const ll MOD=1000000007LL;
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";

int main(){
  ll n,m;cin>>n>>m;
  map<ll,ll>M;
  rep(i,m){
    ll a,b;cin>>a>>b;
    M[a-1]++;
    M[b-1]++;
  }
  rep(i,n)cout<<M[i]<<endl;
}
  

Measured memory_bytes: 256
// ABC148D2.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//

//#include "pch.h"
#include <iostream>
#include<vector>
using namespace std;
int main()
{
	bool one = false;
	int N;
	cin >> N;
	vector<long long>a(N + 1);
	for (int i = 1; i <= N; i++)
	{
		cin >> a.at(i);
		if (a.at(i)==1)
		{
			one = true;
		}
	}
	if (one==false)
	{
		cout << "-1" << endl;
		return 0;
	}
	int size = a.size();
	int j = 1;
	int ai = 1;
	int count = 0;
	while (j<size)
	{
		if (a.at(j)!=ai)
		{
			j++;
			count++;
		}else{
			j++;
			ai++;
		}
	}
	cout << count << endl;
}


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

int main () {
    int N;
    cin >> N;
    vector <int> A(N);
    int MIN = 100;
    for(int i = 0; i < N; i++){
        int count = 0;
        cin >> A[i];
        while(A[i] % 2 == 0){
            A[i] /= 2;
            count++;
        }
        MIN = min(count , MIN);
    }
    cout << MIN << endl;
}


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

using namespace std;
using ll = long long;

int main() {
  int n;
  string s;
  cin >> n >> s;
  int ans = 1;
  for (int i = 1; i < n; i++) {
    if (s[i - 1] != s[i]) {
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3728
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <math.h>
#define MOD 1000000007
typedef long long ll;
using namespace std;

int main(){
  string x;
  cin>>x;
  int n=x.size();

  int s=0,t=0;
  for(int i=0;i<n;i++){
    if(x[i]=='T'){
      if(s>0) s--;
      else t++;
    }else{
      s++;
    }
  }
  cout<<t+s<<endl;
  return 0;
}


Measured memory_bytes: 640
A=[]
x=1.0
y=0.0
for i in range(1001):
    A.append([x,y])
    tmp=(x**2+y**2)**.5
    dx,dy=-y/tmp,x/tmp
    x+=dx
    y+=dy

while 1:
    n=input()
    if n==-1:break
    a,b=A[n-1]
    print "%.2f\n%.2f"%(a,b)

Measured memory_bytes: 4504
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        char[] Str1 = in.nextLine().toCharArray();
        char[] Str2 = in.nextLine().toCharArray();

        in.close();

        int[][] memo = new int[Str1.length + 1][Str2.length + 1];
        for (int i = 1; i <= Str1.length; i++) {
            for (int j = 1; j <= Str2.length; j++) {
                memo[i][j] = Str1[i - 1] == Str2[j - 1]
                        ? memo[i][j] = memo[i - 1][j - 1] + 1
                        : Math.max(memo[i - 1][j], memo[i][j - 1]);
            }
        }


        char[] lcs = new char[memo[Str1.length][Str2.length]];
        int i = Str1.length;
        int j = Str2.length;
        while (memo[i][j] > 0) {
            if (memo[i - 1][j] == memo[i][j]) {
                i = i - 1;
            } else if (memo[i][j - 1] == memo[i][j]) {
                j = j - 1;
            } else {
                i = i - 1;
                j = j - 1;
                lcs[memo[i][j]] = Str1[i];
            }
        }
        System.out.println(new String(lcs));
    }
}


Measured memory_bytes: 83212
#include <iostream>

using namespace std;

int main(){
  int m, f, r;
  while(true){
    cin >> m >> f >> r;
    if(m == -1 && f == -1 && r == -1)break;
    if(m == -1 || f == -1)cout << "F" << endl;
    else if(m + f >= 80)cout << "A" << endl;
    else if(m + f >= 65 && m + f < 80)cout << "B" << endl;
    else if((m + f >= 50 && m + f < 65)||(m + f >= 30 && m + f < 50 && r >= 50))cout << "C" << endl;
    else if(m + f < 50 && m + f >= 30 && r < 50)cout << "D" << endl;
    else if(m + f < 30)cout << "F" << endl;
  }
}



Measured memory_bytes: 3076
N = int(input())
Dp = [a for a in range(N + 1)]
for i in range(1, N + 1):
    for j in range(1,7):
        if i >= (6 ** j):
            Dp[i] = min(Dp[i], Dp[i-6**j] + 1)
    for h in range(1,6):
        if i >= (9 ** h):
            Dp[i] = min(Dp[i], Dp[i-9**h] + 1)
print(Dp[N])    

Measured memory_bytes: 79368
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
#define repi(i,n,init) for(int i=init;i<(int)(n);i++)
#define repd(i,n,init) for(int i=(int)(n);i>=init;i--)
#define repm(i,m) for(auto i=m.begin();i!=m.end();i++)

int main()
{
    string S;
    cin >> S;
    int cnt = 0;
    repi(i,S.length(),0){
        if(S.at(i) == '0'){
            cnt ++;
        }
    }
    cout << 2 * min(cnt,int(S.size())-cnt) << endl;
    return 0;
}

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

using namespace std;

int main()
{
    //freopen("in", "r", stdin);
    //freopen("out", "w", stdout);

    int n = 0;
    scanf("%d", &n);

    printf("%d\n", n * 800 - (n / 15) * 200);
    return 0;
}


Measured memory_bytes: 256
# https://atcoder.jp/contests/abc127/tasks/abc127_c

import itertools
from collections import Counter
from collections import defaultdict
import bisect

def main():
    N, M = map(int, input().split())

    max_l = 0
    min_r = 10 ** 6
    for _ in range(M):
        l, r = map(int, input().split())
        max_l = max(max_l, l)
        min_r = min(min_r, r)

    print(max(0, min_r - max_l + 1))

if __name__ == '__main__':
    main()


Measured memory_bytes: 46696
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Stack stack = new Stack(sc.nextLine());
        stack.printCalcResult();
    }

}

class Stack {

    String[] input = new String[199];
    int[] valStack = new int[100];

    Stack(String text) {
        input = text.split(" ");
    }

    private int calc() {
        int top = 0;
        for(String s: input) {
            switch(s) {
            case "+":
                valStack[top-2] += valStack[top-1];
                top--;
                break;
            case "-":
                valStack[top-2] -= valStack[top-1];
                top--;
                break;
            case "*":
                valStack[top-2] *= valStack[top-1];
                top--;
                break;
            default:
                valStack[top] = Integer.parseInt(s);
                top++;
                break;
            }
        }
        return valStack[0];
    }

    public void printCalcResult() {
        System.out.println(calc());
    }

}


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


int main(){
  unsigned long long N;
  unsigned long long ans = 1;
  cin>>N;
  for (long long int i = 1;i<=N;i++){
    ans = i*ans%1000000007;
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
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; }

// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
//const int mod = 1000000007;
const int mod = 998244353;
struct mint {
  ll x; // typedef long long ll;
  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 { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    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 { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}
// combination mod prime
// https://www.youtube.com/watch?v=8uowVvQ_-Mo&feature=youtu.be&t=1619
struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
};

int main(){
    ios::sync_with_stdio(false);
    int n,m,k;
    cin >> n >> m >> k;
    mint ans = 0;
    mint col = m;
    combination c(n-1);
    for(int x = n-1; x>=0;x--) {
        mint now = col;
        now *=c(n-1,x);
        if(x<=k) ans+=now;
        col*=m-1;
    }
    cout << ans << endl;
}


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

import numpy as np

H, W = map(int, input().split())
S = [str(input()) for _ in range(H)]

S = [-1 if cell == '#' else 0 for s in S for cell in list(s)]
mat = np.reshape(np.array(S), (H, W))

for h in range(H):
    for w in range(W):
        if mat[h, w] == -1:
            if 0 <= h - 1 < H and 0 <= w - 1 < W:
                if mat[h - 1, w - 1] != -1:
                    mat[h - 1, w - 1] += 1
            if 0 <= h - 1 < H and 0 <= w < W:
                if mat[h - 1, w] != -1:
                    mat[h - 1, w] += 1
            if 0 <= h - 1 < H and 0 <= w + 1 < W:
                if mat[h - 1, w + 1] != -1:
                    mat[h - 1, w + 1] += 1
            if 0 <= h < H and 0 <= w - 1 < W:
                if mat[h, w - 1] != -1:
                    mat[h, w - 1] += 1
            if 0 <= h < H and 0 <= w + 1 < W:
                if mat[h, w + 1] != -1:
                    mat[h, w + 1] += 1
            if 0 <= h + 1 < H and 0 <= w - 1 < W:
                if mat[h + 1, w - 1] != -1:
                    mat[h + 1, w - 1] += 1
            if 0 <= h + 1 < H and 0 <= w < W:
                if mat[h + 1, w] != -1:
                    mat[h + 1, w] += 1
            if 0 <= h + 1 < H and 0 <= w + 1 < W:
                if mat[h + 1, w + 1] != -1:
                    mat[h + 1, w + 1] += 1

for h in range(H):
    row = list(mat[h, :])
    for i in row:
        if i == -1:
            print('#', end='')
        else:
            print(i, end='')
    print('')


Measured memory_bytes: 20644
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define mFOR(i, a, b) for (int i = a; i > b; i--)
#define MP make_pair
#define PB push_back
#define N 1000000007
#define INF 10000000000
using namespace std;

typedef long long ll;



int main()
{
    int a, b, t;
    cin >> a >> b >> t;
    cout << (t/a)*b << "\n";
    return 0;
}

Measured memory_bytes: 256
use proconio::input;
use std::collections::BTreeMap;

const M: u64 = 1_000_000_007;

fn main() {
    input! {
        n: usize,
        d: [(i64, i64); n],
    }

    let mut z = 0;
    let mut t = BTreeMap::new();
    for e in d {
        if e.0 == 0 && e.1 == 0 {
            z += 1;
        } else if e.0 == 0 {
            let e = t.entry((0, 1)).or_insert(0);
            *e += 1;
            if *e >= M {
                *e -= M;
            }
        } else if e.1 == 0 {
            let e = t.entry((1, 0)).or_insert(0);
            *e += 1;
            if *e >= M {
                *e -= M;
            }
        } else {
            let g = num::integer::gcd(e.0.abs(), e.1.abs());
            let e = if e.0 < 0 {
                (-e.0, -e.1)
            } else {
                e
            };
            let e = (e.0 / g, e.1 / g);
            let e = t.entry((e.0, e.1)).or_insert(0);
            *e += 1;
            if *e >= M {
                *e -= M;
            }
        }
    }
    z %= M;

    let mut ans = 1;
    while let Some((&k, &c)) = t.iter().next() {
        t.remove(&k);
        let p = if k.1 < 0 {
            (-k.1, k.0)
        } else {
            (k.1, -k.0)
        };

        let c2 = modpow(2, c);
        if let Some(invc) = t.remove(&p) {
            let i2 = modpow(2, invc);
            ans = ans * (c2 + i2 - 1) % M;
        } else {
            ans = ans * c2 % M;
        }
    }
    ans = (ans + z + M - 1) % M;
    println!("{}", ans);
}

fn modpow(x: u64, y: u64) -> u64 {
    let mut result = 1;
    let mut a = x;
    let mut b = y;
    while b > 0 {
        if b % 2 == 1 {
            result = result * a % M;
        }
        a = a * a % M;
        b /= 2;
    }
    result
}


Measured memory_bytes: 20488
#include<iostream>
using namespace std;
void PrintArray(int* a,int n)
{
	for(int i=1;i<n;i++)
	{
		cout<<a[i]<<" ";
	}
	cout<<a[n]<<endl;
}

int main()
{
	int a[101];
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i]; 
	}
	for(int i=1;i<=n;i++)
	{
		a[0]=a[i];
		int j=i;
		while(a[j-1]>a[0])
		{
			a[j]=a[j-1];
			j--;
		}
		a[j]=a[0];
		PrintArray(a,n);
	}
	return 0;
}


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

using namespace std;

const int MAX_V = 200;
const int INF = 1 << 28;

int cost[MAX_V][MAX_V];
int mincost[MAX_V];
bool used[MAX_V];
bool used2[MAX_V];
int V, ans;

void prim_init(int s){
  for(int i=0;i<V;i++){
    mincost[i] = INF;
    used[i] = false;
  }
  ans = mincost[s] = 0;
}

void prim(int s){
  while(1){
    int v = -1;
    for(int u=0;u<V;u++){
      if(used2[u] && !used[u] && (v == -1 || mincost[u] < mincost[v])) v = u;
    }
    if(v == -1) return;
    if(mincost[v] >= INF){
      prim_init(s);
      return;
    }
    used[v] = true;
    ans += mincost[v];
    for(int u=0;u<V;u++){
      mincost[u] = min(mincost[u], cost[v][u]);
    }
  }
}

void init(int n){
  V = n;
  fill(cost[0], cost[MAX_V], INF);
  fill(used2, used2+MAX_V, false);
}

main(){
  int n, m;
  while(cin >> n >> m && (n|m)){
    vector<pair<int, int> > h(n);
    init(n);
    for(int i=0;i<n;i++){
      cin >> h[i].first;
      h[i].second = i;
    }
    for(int i=0;i<m;i++){
      int a, b, c;
      cin >> a >> b >> c;
      --a; --b;
      cost[a][b] = cost[b][a] = c;
    }
    sort(h.begin(), h.end());
    reverse(h.begin(), h.end());
    prim_init(h[0].second);
    bool f = true;
    for(int i=0;i<n;i++){
      used2[h[i].second] = true;
      int j = i + 1;
      for(;j<n&&h[j].first==h[i].first;j++) used2[h[j].second] = true;
      i = j - 1;
      prim(h[i].second);
    }
    cout << ans << endl;
  }
}

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

# define rep(i, n) for(int(i)=0;(i)<(n);(i)++)
# define reps(i, n) for(int(i)=1;(i)<=(n);(i)++)
# define rrep(i, n) for(int i=((int)(n)); i>0; --i)
# define rreps(i, n) for(int i=((int)(n)); i>=0; --i)
# define ALL(v) v.begin(), v.end()
template<class T>inline bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>inline bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<typename T> void dump(T e){std::cout << e << std::endl;}
template<typename T> void dump(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void dump(const std::vector<std::vector<T> >& vv){ for(const auto& v : vv){ dump(v); } }
typedef long long ll;

int main() {
  string S; cin >> S;
  cout << S[0] << S.size()-2 << S[S.size()-1] << endl;
}

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

int main() {
  int A, B;
  cin >> A >> B;
  int amari = (B-1) % (A-1);
  
  if (amari != 0) {
    cout << (B-1) / (A-1) + 1 << endl;
  }
  else {
    cout << (B-1) / (A-1) << endl;
  }
}

Measured memory_bytes: 256
/*
ЗАПУСКАЕМ 
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░ 
 */
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>

using namespace std;
template<typename T1, typename T2> inline void chkmin(T1 &a, T2 b) {if (a > b) a = b;}
template<typename T1, typename T2> inline void chkmax(T1 &a, T2 b) {if (a < b) a = b;}
#define files(FILENAME) read(FILENAME); write(FILENAME)
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define all(c) (c).begin(), (c).end()
#define sz(c) (int)(c).size()
#define left left228
#define right right228
#define y1 y1228
#define mp make_pair
#define pb push_back
#define y2 y2228
const string FILENAME = "input";







vector<int> get(int a, int b, int n) {
	if (n == 1) {
		//cout << a << ' ' << b << endl;
		if (a + b != 1) {
			cout << "NO\n";
			exit(0);	
		}
		vector<int> res;
		res.pb(a);
		res.pb(b);
		return res;
	}
	int a1 = 0, b1 = 0;
	int pos = -1;
	vector<int> g;
	for (int i = 0; i < n; i++) {
		if ((a ^ b) & (1 << i)) {
			pos = i;
			int uk = 0;
			for (int j = 0; j < n; j++) {
				if (i != j) {
					if (a & (1 << j)) {
						a1 += 1 << uk;
					}
					if (b & (1 << j)) {
						b1 += 1 << uk;
					}
					g.pb(j);
					uk++;
				}
			}
			break;
		} 
	}
	if (pos == -1) {
		cout << "NO\n";
			exit(0);
	}
	vector<int> res1 = get(a1, a1 ^ 1, n - 1);
	vector<int> res2 = get(a1 ^ 1, b1, n - 1);
	vector<int> res;
	for (auto x: res1) {
		int nx = 0;
		for (int f = 0; f < n - 1; f++) {
			if (x & (1 << f)) {
				nx += 1 << g[f];
			}
		}
		if (a & (1 << pos)) {
			nx += 1 << pos;
		}
		res.pb(nx);
	}
	for (auto x: res2) {
		int nx = 0;
		for (int f = 0; f < n - 1; f++) {
			if (x & (1 << f)) {
				nx += 1 << g[f];
			}
		}
		if (b & (1 << pos)) {
			nx += 1 << pos;
		}
		res.pb(nx);
	}
	return res;
}

int  main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
  //  read(FILENAME);
    int n, a, b;
	cin >> n >> a >> b;
	vector<int> res = get(a, b, n);
	cout << "YES\n";
	for (auto x: res) {
		cout << x << ' ';
	}
	cout << '\n';
 	return 0; 
}


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

vector<int64_t> enumDivisor(int64_t n)
{
  vector<int64_t> res;
  for (int64_t i = 1; i * i <= n; i++)
  {
    if (n % i != 0)
      continue;
    res.push_back(i);
    if (i * i != n)
      res.push_back(n / i);
  }
  return res;
}

int main()
{
  int64_t N;
  cin >> N;
  int64_t ans = 0;
  for (int64_t x : enumDivisor(N))
  {
    if (x == 1)
      continue;
    int64_t tmp = N;
    while (tmp % x == 0)
      tmp /= x;
    tmp %= x;
    if (tmp == 1)
      ans++;
  }
  ans += enumDivisor(N - 1).size() - 1;
  cout << ans << endl;
}


Measured memory_bytes: 3732
// 解説記事を読んで書いたもの
// 参考: http://kazune-lab.net/contest/2019/01/20/abc116/
// 参考: https://atcoder.jp/contests/abc116/submissions/4053275

#include <iostream>
using namespace std;

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

    int h[N + 1];
    for (int i = 0; i < N; i++)
    {
        cin >> h[i];
    }

    int ans = 0;
    // i : h[i]>0となる最小の添字
    for (int i = 0; i < N; i++)
    {
        while (h[i] > 0)
        {
            // h[i] から h[j] までが一回の操作で同時に高さを減らせるかたまり
            for (int j = i; j < N; j++)
            {
                if (h[j] > 0)
                {
                    h[j]--;
                }
                else
                {
                    break;
                }
            }
            ans++;
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#include<unordered_map>
#pragma warning(disable:4996)
using namespace std;


pair<int, int>memo[33][33][33][33];

int field[32][32];
int sum[33][33];


int getsum(int l, int r, int u, int d) {
	return sum[d][r] - sum[u][r] - sum[d][l] + sum[u][l];
}

pair<int,int> getans(const int l, const int r, const int u, const int d, const int rest) {
	if (memo[l][r][u][d].first != -1)return memo[l][r][u][d];
	const int sum(getsum(l, r, u, d));
	if (sum < rest)return memo[l][r][u][d] = make_pair(0, 0);
	else if(sum<2*rest)return memo[l][r][u][d] = make_pair(1, sum-rest);
	else {
		pair<int, int>ans= make_pair(1, sum - rest);
		for (int y = u + 1; y < d; ++y) {
			pair<int, int>a(getans(l, r, u, y, rest));
			pair<int, int>b(getans(l, r, y, d, rest));
			if (a.first > 0 && b.first>0) {
				pair<int, int>nans = make_pair(a.first + b.first, min(a.second, b.second));
				ans = max(ans, nans);
			}
		}
		for (int x = l + 1; x < r; ++x) {
			pair<int, int>a(getans(l, x, u, d, rest));
			pair<int, int>b(getans(x, r, u, d, rest));
			if (a.first > 0 && b.first>0) {
				pair<int, int>nans = make_pair(a.first + b.first, min(a.second, b.second));
				ans = max(ans, nans);
			}
		}
		return memo[l][r][u][d] = ans;
	}
}
int H, W;

int main() {
	while (1) {
		for (int i = 0; i < 33; ++i) {
			for (int j = 0; j < 33; ++j) {
				for (int k = 0; k < 33; ++k) {
					for (int l = 0; l < 33; ++l) {
						memo[i][j][k][l] = make_pair(-1, -1);
					}
				}
			}
		}
		int S;
		cin >> H >> W >> S;
		if (!H)break;
		memset(field, 0, sizeof(field));
		memset(sum, 0, sizeof(sum));

		for (int i = 0; i < H; ++i) {
			for (int j = 0; j < W; ++j) {
				int a; cin >> a;
				field[i][j] = a;
			}
		}
		for (int i = 0; i < H; ++i) {
			for (int j = 0; j < W; ++j) {
				sum[i + 1][j + 1] = sum[i][j + 1] + sum[i + 1][j] - sum[i][j] + field[i][j];
			}
		}
		int over = sum[H][W] - S;
		pair<int, int>ans(getans(0, W, 0, H, over));
		cout << ans.first << " " << ans.second << endl;
	}
	return 0;
}

Measured memory_bytes: 12372
object Main extends App {
  val sc = new java.util.Scanner(System.in)
  val n = sc.nextInt()
  val a = List.fill(n)(sc.nextInt()).sorted

  val mod = 1000000007

  def plus(a: Long, b: Long): Long = (a + b) % mod
  def times(a: Long, b: Long): Long = (a * b) % mod

  def pow(a: Long, n: Int, res: Long = 1): Long = {
    if (n == 0) {
      res
    } else if ((n&1) == 0) {
      pow(times(a,a), n >> 1, res)
    } else {
      pow(times(a,a), n >> 1, times(res,a))
    }
  }

  if (n % 2 == 0) {
    val b = (1 until n by 2).flatMap(i => List(i, i))
    if (a == b) {
      println(pow(2, n/2))
    } else {
      println(0)
    }
  } else {
    val b = (0 until n by 2).flatMap(i => List(i, i)).tail
    if (a == b) {
      println(pow(2, (n-1)/2))
    } else {
      println(0)
    }
  }
}


Measured memory_bytes: 66532
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<map>
#include<string.h>
#include<complex>
#include<math.h>
#include<queue>
#include <functional>
#include<time.h>
#include <stack>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define ll long long
#define llint long long int
#define sort(s) sort(s.begin(),s.end())
#define reverse(v)  reverse(v.begin(), v.end());
#define Yes(ans) if(ans)cout<<"Yes"<<endl; else cout<<"No"<<endl;
#define YES(ans) if(ans)cout<<"YES"<<endl; else cout<<"NO"<<endl;
#define hei(a) vector<a>
#define whei(a) vector<vector<int>>
constexpr auto mod = 1000000007;


//2のn乗を求めるよ！！！
int ni(int n) {
	if (n == 0)return 1;
	int x = ni(n / 2);
	x *= x;
	if (n % 2 == 1)x *= 2;
	return x;
}

//フィボナッチ数列のx番目を求めるよ！
int f(int x, vector<int> s) {
	if (x == 0)return 0;
	if (x == 1)return 1;
	if (s[x] != 0)return s[x];
	s[x] = f(x - 1, s) + f(x - 2, s);
	return s[x];
}

//aとｂの最大公約数を求めるよ！
llint gcd(llint a, llint b) {
	if (a < b)swap(a, b);
	if (b == 0)return a;
	return gcd(b, a % b);
}



// a^n mod を計算する
long long modpow(long long a, long long n, long long mod) {
	long long res = 1;
	while (n > 0) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}

// mod. m での a の逆元 a^{-1} を計算するよ！
long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}


//aCbをmod.mで割った余りを求める
ll int c(ll int a, ll int b, ll int m) {
	ll int ans = 1;
	for (ll int i = 0; i < b; i++) {
		ans *= a - i;
		ans %= m;
	}
	for (ll int i = 1; i <= b; i++) {
		ans *= modinv(i, m);
		ans %= m;
	}
	return ans;
}

//m進数のn桁を全列挙やで
void dfs(int m, int n) {

	stack<string> st;
	st.push("");
	while (!st.empty()) {
		string now = st.top();
		st.pop();
		if (now.size() == n) {
			cout << now << endl;
		}
		else {
			for (int i = m - 1; i >= 0; i--) {
				string next = now + to_string(i);
				st.push(next);
			}
		}
	}
}
void press(string& v) { v.erase(unique((v).begin(), (v).end()), v.end()); }

int main() {
	int n;
	cin >> n;
	hei(int) a(n+1,1000000000);
	rep(i, 0, n)cin >> a[i];
	int x = 1;
	int ans = 0;
	sort(a);
	a[n] = 0;
	rep(i, 0,n ) {
		if (a[i] == a[i + 1])x++;
		else {
			if (x % 2 == 1)ans++;
			x = 1;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 1e9;
int main(){
  int H,W; cin >> H >> W; int b = 0;
  vector<vector<char>> S(H,vector<char>(W)); 
  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){ 
      cin >> S[i][j]; if(S[i][j] == '#'){ b++;}}}
  
  vector<vector<int>> dist(H,vector<int>(W,INF));
  
  queue<pair<int,int>> Q; Q.push(make_pair(0,0)); dist[0][0] = 1;
  
  int dx[] = {1,0,-1,0}; int dy[] = { 0,1,0,-1};
  
  while(!Q.empty()){
    pair<int,int> p = Q.front(); Q.pop();
    for(int k = 0; k < 4; k++){
      int x = p.first + dx[k]; int y = p.second + dy[k];
      if( x < 0 | x >= H || y < 0 || y >= W){ continue;}
      if( S[x][y] == '#'){ continue;}
      if( dist[x][y] != INF){ continue;}
      dist[x][y] = dist[p.first][p.second] + 1; Q.push(make_pair(x,y));}
  }
    if(dist[H-1][W-1] == INF){ cout << -1 << endl; return 0;}
    
    cout << H*W-b-dist[H-1][W-1] << endl; return 0;}

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

#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define TRACE(x) cerr << #x << " = " << x << endl
#define _ << " _ " <<

#define x first
#define y second
#define pb push_back

using namespace std;

typedef long long ll;

const int MAXN = 100100;

char S[MAXN];

int main(void) {
  ios_base::sync_with_stdio(false);
  cin >> S;
  int N = strlen(S);

  for (int i = 0; i < N; ++i) {
    if (i > 0 && S[i] == S[i-1]) {
      cout << i << " " << i+1 << endl;
      return 0;
    }
    if (i > 1 && S[i] == S[i-2]) {
      cout << i-1 << " " << i+1 << endl;
      return 0;
    }
  }

  cout << "-1 -1" << endl;

  return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define REP(i, s, n) for (int i = s; i < n; i++)
#define ALL(a) a.begin(), a.end()
#define MOD 1000000007
using namespace std;
typedef long long ll;

int main() {
    int N, M; cin >> N >> M;
    vector<int> X(M);
    REP(i, 0, M) cin >> X[i];
    sort(ALL(X));

    vector<int> diff(M - 1);
    REP(i, 0, M - 1) diff[i] = X[i + 1] - X[i];
    sort(ALL(diff), greater<int>());

    int res = X[M - 1] - X[0];
    REP(i, 0, min(N - 1, (int)diff.size())) res -= diff[i];
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>

using namespace std;

int main()
{
		int p, n;
		cin >> p >> n;
		int numbers[n];
		int maxdist = 0, sum = 0;
		for (int i = 0; i < n; i++)
		{
			cin >> numbers[i];
		}
		for (int i = 0; i < n-1; i++)
		{
			int d = abs(numbers[i] - numbers[i+1]);
			if (d > maxdist)
			{
				maxdist = d;
			}
			sum += d;
		}
		int lastd = numbers[0] + (p - numbers[n-1]);
		if (lastd > maxdist) maxdist = lastd;
		cout << sum - maxdist + lastd;
		
}

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

using namespace std;

int main() {
    string s, t;
    cin >> s >> t;
    
    sort(t.begin(), t.end(), greater<char>());
    sort(s.begin(), s.end());

    if (s < t)
        cout << "Yes" << endl;
    else 
        cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3596
#define _USE_NATH_DEFINES
#include <iostream>
#include<algorithm>
using namespace std;

int main() {
	int A[3];
	int n = 3;
	for (int i = 0; i < n; i++) {
		cin >> A[i];
	}
	sort(A, A + n);
	if (A[0] + A[1] + A[2] == 17 && A[0] == 5 && A[1] == 5) cout << "YES" << endl;
	else cout << "NO" << endl;
	return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using System.Globalization;
using System.Diagnostics;

namespace atcoder
{
    class Solver
    {
        public Solver() { }

        public static int Main()
        {
            new Solver().Solve();
            return 0;
        }

        Scanner cin;
        public void Solve()
        {
            cin = new Scanner();
            int A = cin.nextInt();
            int B = cin.nextInt();
            int C = cin.nextInt();

            int n = 0;
            while (true)
            {
                if (n == C)
                {
                    Console.Write(n);
                    return;
                }

                if (B >= A)
                {
                    B = B - A;
                    n++;
                }
                else
                {
                    Console.Write(n);
                    return;
                }
            }
        }
    }

    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: 11092
#include<bits/stdc++.h>
using namespace std;

long long t[200000];

int main(){

    int n;
    cin >> n;

    for(int i=0;i<n;i++){
        cin >> t[i];
    }

    if(n%2==0){
        for(int i=n;i!=0;i-=2){
            cout << t[i-1] << " ";
        }
        for(int i=0;i<n-3;i+=2){
            cout << t[i] << " ";
        }
        cout << t[n-2] << endl;
    }
    else if(n==1){
        cout << t[0] << endl;
    }
    else{
        for(int i=n;i!=-1;i-=2){
            cout << t[i-1] << " ";
        }
        for(int i=1;i<n-3;i+=2){
            cout << t[i] << " ";
        }
        cout << t[n - 2] << endl;

    }
    return 0;

}

Measured memory_bytes: 3712
n = int(input())
A = list(map(int,input().split()))

tot = sum(A)
epi = tot
pre = 0
dif = tot
for i in range(n):
	pre += A[i]
	epi -= A[i]

	if abs(pre-epi) > dif:
		break
	else:
		dif = abs(pre-epi)

print(dif)

Measured memory_bytes: 26764
n=int(input())
bx=by=bt=0
ans='Yes'

for i in range(n):
    t,x,y=map(int, input().split())
    if t%2!=(x+y)%2:
        ans='No'
    if abs(bx-x)+abs(by-y)>abs(bt-t):
        ans='No'
    bx=x
    by=y
    bt=t

print(ans)

Measured memory_bytes: 9096
import collections
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    a_list = list([int(input()) for _ in range(N)])
    a_freq = collections.Counter(a_list)
    print(len([freq for freq in a_freq.values() if freq % 2 == 1]))

if __name__ == '__main__':
    main()

Measured memory_bytes: 57560
import sys
from pprint import pprint

def solve():
    readline = sys.stdin.readline
    H, W, M = map(int, readline().split())

    xy = [list(map(int, readline().split())) for i in range(M)]

    xs = {}
    ys = {}
    #debug = [['.'] * W for i in range(H)]
    for x,y in xy:
        if x not in xs:
            xs[x] = []
        xs[x].append((x, y))

        if y not in ys:
            ys[y] = []
        ys[y].append((x ,y))

        #debug[x-1][y-1] = '#'
    
    #pprint(debug)
    
    max_len_xs = max(len(v) for v in xs.values())
    max_len_ys = max(len(v) for v in ys.values())

    xs = {k: v for k,v in xs.items() if len(v) == max_len_xs}
    ys = {k: v for k,v in ys.items() if len(v) == max_len_ys}


    cy = {k: sum(1 if x in xs else 0 for x,y in v)
        for k,v in ys.items()}

    nn = len(xs)
    if all(v == nn for v in cy.values()):
        print(max_len_xs + max_len_ys - 1)
    else:
        print(max_len_xs + max_len_ys)
    

    #for v in xs.values():
    #    for x,y in v:
    #        if y in cy:
    #            cy[y] -= 1
    
    
    #print(cy)
    #if all(c == 0 for c in cy.values()):
    #    print(max_len_xs + max_len_ys - 1)
    #else:
    #    print(max_len_xs + max_len_ys)

solve()

Measured memory_bytes: 322660