#include<iostream>
using namespace std;

int ex_gcd(int a,int b,int &x,int &y){
	if(b==0){
		x=1;
		y=0;
		return a;
	}
	int d = ex_gcd(b,a%b,x,y);
	int t = y;
	y = x-a/b*y;
	x = t;
	return d;
}//x,y满足ax+by=gcd(a,b)的其中一组解

int minnotleg(int a,int b,int c){
	//ax+by=c的最小整数解 
	int x,y,d;
	int g=ex_gcd(a,b,x,y);

	x*=c/g;
	y*=c/g;
	d=abs(b/g);
	return (x%d+d)%d;
}

int main(){
	return 0;
}