stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <iostream>

#include <stdlib.h>

#include <iomanip>

//#include <string.h>



using namespace std;



int main()

{

    int n,a[100],i,ass=0;

    cin>>n;

    for(i=1;i<=n;i++)

    {

        cin>>a[i];

    }

    for(i=1;i<=n;i++)

    {

        if(a[i]!=i)

            ass++;

    }

    if(ass>2)

        cout<<"NO";

    else

        cout<<"YES";

    return 0;

}


// Optimized solution to the same problem (faster):
#include<stdio.h>



int main()

{

    int n, i, ans=1, j=1;



    scanf("%d", &n);



    int P[n+2];



    for(i=1; i<=n ; i++){

        scanf("%d", &P[i]);

        if(i != P[i]){

            if(j==3){

                ans=0;

                break;

            }

            j++;

        }

    }



    if(ans)

        printf("YES\n");

    else

        printf("NO\n");



    return 0;

}




// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <cmath>

#include <cstdio>

#include <vector>

#include <cstdlib>

#include <cassert>

#include <cstring>

#include<stdio.h>

#include <iostream>

#include <algorithm>

#include<bits/stdc++.h>

#define endl "\n"

#define hs ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

typedef long long ll;

using namespace std;

#define ll long long int

#define pb push_back

#define mp make_pair

#define all(x) x.begin(),x.end()



int main()

{

    int i,x,n,j,flag,temp=0;

    cin>>n;

    int a[n];



    for (i=0; i<n; i++)

    {

        cin>>a[i];

    }

    for(i=0; i<n; i++)

    {

        if(a[i]!=i+1)

        {

            flag=1;

            break;

        }

    }

    for(j=0; j<n; j++)

    {

        if(a[j]==i+1)

        {

            break;

        }

    }

    if (flag==1)

    {

        x=a[i];

        a[i]=a[j];

        a[j]=x;

    }



    for(i=0; i<n-1 ; i++)

    {

        if(a[i]>a[i+1])

        {

            cout<<"NO"<<"\n";

            temp=1;

            break;

        }

    }

    if (temp==0)

        cout<<"YES"<<"\n";

    return 0;

}




// Optimized solution to the same problem (faster):
#include<stdio.h>



int main()

{

    int n, i, ans=1, j=1;



    scanf("%d", &n);



    int P[n+2];



    for(i=1; i<=n ; i++){

        scanf("%d", &P[i]);

        if(i != P[i]){

            if(j==3){

                ans=0;

                break;

            }

            j++;

        }

    }



    if(ans)

        printf("YES\n");

    else

        printf("NO\n");



    return 0;

}




// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

using namespace std;

int main(){

int n,i,f=0;

cin>>n;

int p[n];

  for( i=1;i<=n;i++){

    cin>>p[i];

  }

  i=0;

   for(i=1;i<=n;i++){

if(p[i]!=i){f++;}

    }

    if(f<=2){

    cout<<"YES"<<endl;

}

else{

    cout<<"NO"<<endl;

}







}


// Optimized solution to the same problem (faster):
#include<stdio.h>



int main()

{

    int n, i, ans=1, j=1;



    scanf("%d", &n);



    int P[n+2];



    for(i=1; i<=n ; i++){

        scanf("%d", &P[i]);

        if(i != P[i]){

            if(j==3){

                ans=0;

                break;

            }

            j++;

        }

    }



    if(ans)

        printf("YES\n");

    else

        printf("NO\n");



    return 0;

}




// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>



using namespace std;



int main()

{

    int n,ara[52],flag=0;

    cin>>n;



    for(int i=1;i<=n;i++)

    {

        cin>>ara[i];

    }



    for(int i=1;i<=n;i++)

    {

        if(ara[i]!=i)

        {

            flag++;

        }

    }



    if(flag==0 || flag==2)

    {

        cout<<"YES"<<endl;

    }

    else

        cout<<"NO"<<endl;



    return 0;

}


// Optimized solution to the same problem (faster):
#include<stdio.h>



int main()

{

    int n, i, ans=1, j=1;



    scanf("%d", &n);



    int P[n+2];



    for(i=1; i<=n ; i++){

        scanf("%d", &P[i]);

        if(i != P[i]){

            if(j==3){

                ans=0;

                break;

            }

            j++;

        }

    }



    if(ans)

        printf("YES\n");

    else

        printf("NO\n");



    return 0;

}




// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>



void Sort(int a[], int n) 

{

   int i, j, min, temp;

   for (i = 0; i < n - 1; i++) {

      min = i;

      for (j = i + 1; j < n; j++)

      if (a[j] < a[min])

      min = j;

      temp = a[i];

      a[i] = a[min];

      a[min] = temp;

   }

}

int main()

{

	int n,wrong=0;

	std::cin>>n;

	int arr[n],sortedarr[n];

	for(int i=0;i<n;i++)

	{

		std::cin>>arr[i];

		sortedarr[i]=arr[i];

	}	

	Sort(sortedarr,n);

	for(int i=0;i<n;i++)

	{

		if(arr[i]!=sortedarr[i])

			wrong++;

	}

	if(wrong<=2)

		std::cout<<"YES";

	else

		std::cout<<"NO";



	return 0;

}


// Optimized solution to the same problem (faster):
#include<stdio.h>



int main()

{

    int n, i, ans=1, j=1;



    scanf("%d", &n);



    int P[n+2];



    for(i=1; i<=n ; i++){

        scanf("%d", &P[i]);

        if(i != P[i]){

            if(j==3){

                ans=0;

                break;

            }

            j++;

        }

    }



    if(ans)

        printf("YES\n");

    else

        printf("NO\n");



    return 0;

}




// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>



using namespace std;



#define ll long long

#define endl "\n"



int main()

{

    ll n;

    cin >> n;

    ll a[n], b[n];

    for (ll i = 0; i < n; ++i)

        cin >> a[i], b[i] = a[i];

    sort(b, b + n);

    ll ans = 0;

    for (ll i = 0; i < n; ++i)

    {

        if (a[i] != b[i])

            ++ans;

    }

    if (ans > 2)

    {

        cout << "NO\n";

        return 0;

    }

    cout << "YES\n";

    return 0;

}


// Optimized solution to the same problem (faster):
#include<stdio.h>



int main()

{

    int n, i, ans=1, j=1;



    scanf("%d", &n);



    int P[n+2];



    for(i=1; i<=n ; i++){

        scanf("%d", &P[i]);

        if(i != P[i]){

            if(j==3){

                ans=0;

                break;

            }

            j++;

        }

    }



    if(ans)

        printf("YES\n");

    else

        printf("NO\n");



    return 0;

}




// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

 

int main() {

	int n, count=0;

	std::cin>>n;

	int* ara = new int[n]; 

	int* arb = new int[n];

 

	for(int i=0; i<n; i++){

        std::cin>>ara[i];

        arb[i]=ara[i];

    }

 

	std::sort(ara, ara+n);

 

	for(int i=0; i<n; i++) if(ara[i]!=arb[i]) count++;

 

	if(count==2 || count==0) std::cout<<"YES";

	else std::cout<<"NO";

}

// Optimized solution to the same problem (faster):
#include<stdio.h>



int main()

{

    int n, i, ans=1, j=1;



    scanf("%d", &n);



    int P[n+2];



    for(i=1; i<=n ; i++){

        scanf("%d", &P[i]);

        if(i != P[i]){

            if(j==3){

                ans=0;

                break;

            }

            j++;

        }

    }



    if(ans)

        printf("YES\n");

    else

        printf("NO\n");



    return 0;

}




// Fastest known solution for this problem:
// Original C++ solution (slower):
//  ©   ___MRX___



#include <bits/stdc++.h>

    using namespace std;



#define ll long long int



int main()

{

    int n, i, flag = 0;

    cin >> n;

    vector<int> vec(n);

    for(i = 0; i < n; i++) {

        cin >> vec[i];

    }

    for(i = 0; i < n; i++) {

        if(vec[i] != i + 1) flag++;

    }



    if(flag <= 2) cout << "YES" << "\n";

    else cout << "NO" << '\n';



    return 0;

}


// Optimized solution to the same problem (faster):
#include<stdio.h>

#define size 55

int main()

{

    int i,j,n,a[size],cnt=0;

    scanf("%d",&n);

    for(i=0;i<n;i++)

    {

        scanf("%d",&a[i]);

    }

    for(i=0;i<n;i++)

    {

        if(a[i]!=i+1)cnt++;

    }

    if(cnt<=2)printf("YES");

    else printf("NO");

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

int in(void){

	int i;scanf("%d",&i);

	return i;

}

int main(void){

	int a=in(),b=in();

	if(a%3==0||b%3==0||(a+b)%3==0){

		puts("Possible");

	}

	else{

		puts("Impossible");

	}

	return 0;

}

// Optimized solution to the same problem (faster):
#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <math.h>

#include <ctype.h>

#include <limits.h>	

#define inf (INT_MAX-1)

#define INF 9223372036854775807

#define sq(n) ((n)*(n))

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

#define rev(i,n) for(i=n-1;i>=0;i--)

const int mod=(int)1e09+7;

 

int in(void){

	int i;scanf("%d",&i);

	return i;

}

long long llin(void){

	long long i;scanf("%lld",&i);

	return i;

}

double din(void){

	double i;scanf("%lf",&i);

	return i;

}

void chin(char s[]){

	scanf("%s",s);

}

void print(int a){

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

}

void llprint(long long a){

	printf("%lld\n",a);

}

void dprint(double a){

	printf("%.10f\n",a);

}

void print2(int a,int b){

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

}

long long max(long long a,long long b){

	return a>b?a:b;

}

long long min(long long a,long long b){

	return a<b?a:b;

}

double dmax(double a,double b){

	return a>b?a:b;

}

int cmp(const void *a,const void *b){

	return *(long long *)a-*(long long *)b;

}

 

int main(void){

	int a=in(),b=in();

	if(a%3==0||b%3==0||(a+b)%3==0){

		puts("Possible");

	}

	else{

		puts("Impossible");

	}

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#define rep(i,a,b) for(register int i(a);i <= b;i++)

#define ll long long

using namespace std;

int main()

{

	//freopen("robot.in","r",stdin);

	//freopen("robot.out","w",stdout);

	int n,x,k(0);ll ans(1);

	cin>>n;

	rep(i,1,n)

	{

		scanf("%d",&x);

		++k;

		if(x < (k << 1) - 1) ans *= k,ans %= 1000000007,--k;

	}

	while(k != 1) ans *= k,ans %= 1000000007,--k;

	printf("%lld",ans);

	return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

using namespace std;

long long m,v[100001];

long long ans=1,cnt=0,p=0,k=1;

int main()

{

//	freopen("robot.in","r",stdin);

//	freopen("robot.out","w",stdout);

	scanf("%lld",&m);

	for(int i=1;i<=m;i++)

	{

	scanf("%lld",&v[i]);

	int z=(v[i-1]+1)/2-(i-1);

	while(z<p)

	{

		ans=ans*cnt%1000000007;

		cnt--;

		p--;

		k++;

	}

	cnt++;

	}

	for(;k<=m;k++)

	ans=ans*(cnt--)%1000000007;

	printf("%lld",ans);

//	fclose(stdin);

//	fclose(stdout);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

using namespace std;



int cost[101][101],t[101][101];

bool tf,cf;



int wf(int p,int q,int r,int m){

	if(r){

		if(tf){

		for(int k=1 ; k <= m ; ++k){

			for(int i=1 ; i <= m ; ++i){

				for(int j=1 ; j <= m ; ++j){

					if(t[i][j] > t[i][k] + t[k][j]) t[i][j] = t[i][k] + t[k][j];

				}

			}

		}

		tf = false;

			return t[p][q];

		}

		else return t[p][q];

		}

		else if(cf){

		for(int k=1 ; k <= m ; ++k){

			for(int i=1 ; i <= m ; ++i){

				for(int j=1 ; j <= m ; ++j){

					if(cost[i][j] > cost[i][k] + cost[k][j]) cost[i][j] = cost[i][k] + cost[k][j];

				}

			}

		}

		cf = false;

		return cost[p][q];

	}

	else return cost[p][q];

}



int main(){

	int a,b,c,d,n,m,k,p,q,r;

	

	while(cin >> n >> m && n && m){

		for(int i=1 ; i <= m ; ++i){

			for(int j=1 ; j <= m ; ++j){

				cost[i][j] = 10000;

				t[i][j] = 10000;

			}

		}

		cf = true;

		tf = true;

		for(int i=0 ; i < n ; ++i){

			cin >> a >> b >> c >> d;

			cost[a][b] = c;

			cost[b][a] = c;

			t[a][b] = d;

			t[b][a] = d;

		}

		cin >> k;

		for(int i=0 ; i < k ; ++i){

			cin >> p >> q >> r;

			cout << wf(p,q,r,m) << endl;

		}

	}

	return 0;

} 

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>



using namespace std;



int main(void){

	int floy[101][101][2];

	while(1){

		int n,m;

		scanf("%d%d",&n,&m);

		if(n==0&&m==0){

			break;

		}

			

		for(int b=0;b<2;b++){

			for(int i=0;i<=m;i++){

				for(int j=0;j<=m;j++){

					floy[i][j][b]=1<<29;

				}

			}

		}

		

		for(int i=0;i<n;i++){

			int a,b,cost,time;

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

			floy[a][b][0]=cost;

			floy[b][a][0]=cost;

			floy[a][b][1]=time;

			floy[b][a][1]=time;

		}

		

		for(int b=0;b<2;b++){

			for(int k=1;k<=m;k++){

				for(int i=1;i<=m;i++){

					for(int j=1;j<=m;j++){

							floy[i][j][b]=min(floy[i][j][b],floy[i][k][b]+floy[k][j][b]);

					}

				}

			}

		}

		

		

		int kazu;

		scanf("%d",&kazu);

		

		for(int i=0;i<kazu;i++){

			int a,b,c;

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

			printf("%d\n",floy[a][b][c]);

		}

	}

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

using namespace std;



int cost[101][101],t[101][101];

bool tf,cf;



int wf(int p,int q,int r,int m){

	if(r){

		if(tf){

			for(int k=1 ; k <= m ; ++k){

				for(int i=1 ; i <= m ; ++i){

					for(int j=1 ; j <= m ; ++j){

						if(t[i][j] > t[i][k] + t[k][j]) t[i][j] = t[i][k] + t[k][j];

					}

				}

			}

			tf = false;

			return t[p][q];

		}else return t[p][q];

	}else if(cf){

		for(int k=1 ; k <= m ; ++k){

			for(int i=1 ; i <= m ; ++i){

				for(int j=1 ; j <= m ; ++j){

						if(cost[i][j] > cost[i][k] + cost[k][j]) cost[i][j] = cost[i][k] + cost[k][j];

				}

			}

		}

		cf = false;

		return cost[p][q];

	}

	else return cost[p][q];

}



int main(){

	int a,b,c,d,n,m,k,p,q,r;

	

	while(cin >> n >> m && n && m){

		for(int i=1 ; i <= m ; ++i){

			for(int j=1 ; j <= m ; ++j){

				cost[i][j] = 10000;

				t[i][j] = 10000;

			}

		}

		cf = true;

		tf = true;

		for(int i=0 ; i < n ; ++i){

			cin >> a >> b >> c >> d;

			cost[a][b] = c;

			cost[b][a] = c;

			t[a][b] = d;

			t[b][a] = d;

		}

		cin >> k;

		for(int i=0 ; i < k ; ++i){

			cin >> p >> q >> r;

			cout << wf(p,q,r,m) << endl;

		}

	}

	return 0;

} 

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>



using namespace std;



int main(void){

	int floy[101][101][2];

	while(1){

		int n,m;

		scanf("%d%d",&n,&m);

		if(n==0&&m==0){

			break;

		}

			

		for(int b=0;b<2;b++){

			for(int i=0;i<=m;i++){

				for(int j=0;j<=m;j++){

					floy[i][j][b]=1<<29;

				}

			}

		}

		

		for(int i=0;i<n;i++){

			int a,b,cost,time;

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

			floy[a][b][0]=cost;

			floy[b][a][0]=cost;

			floy[a][b][1]=time;

			floy[b][a][1]=time;

		}

		

		for(int b=0;b<2;b++){

			for(int k=1;k<=m;k++){

				for(int i=1;i<=m;i++){

					for(int j=1;j<=m;j++){

							floy[i][j][b]=min(floy[i][j][b],floy[i][k][b]+floy[k][j][b]);

					}

				}

			}

		}

		

		

		int kazu;

		scanf("%d",&kazu);

		

		for(int i=0;i<kazu;i++){

			int a,b,c;

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

			printf("%d\n",floy[a][b][c]);

		}

	}

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<cstdio>

#include<algorithm>

#include<queue>



#define INF 1<<29



class state{

	public:

	int p,v;

	state(){}

	state(int a,int b){

		p=a;v=b;

	}

	bool operator < (const state &a) const{

		return v > a.v;

	}

};

using namespace std;



int main(){

	while(1){

		int n,m;

		scanf("%d%d",&m,&n);

		if(n==0 && m==0){

			break;

		}

		int cost[101][101];

		int time[101][101];

		

		for(int i=0;i<101;i++)

		for(int j=0;j<101;j++)

		cost[i][j]=time[i][j]=INF;

		

		for(int i=0;i<m;i++){

			int a,b,c,d;

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

			cost[a][b]=cost[b][a]=c;

			time[a][b]=time[b][a]=d;

		}

		

		scanf("%d",&m);

		for(int i=0;i<m;i++){

			int st,en,va;

			scanf("%d%d%d",&st,&en,&va);

			

			priority_queue<state> aa;

			

			int meen[101];

			int visit[101]={0};

			

			for(int i=0;i<101;i++){meen[i]=INF;}

			

			aa.push(state(st,0));

			meen[st]=0;

			int ans=0;

			while(1){

				state u = aa.top();

				aa.pop();

				

				if(u.p==en){

					ans=u.v;

					break;

				}

				

				visit[u.p]=1;

				

				for(int i=1;i<=n;i++){

					if(visit[i]==0){

						int val=cost[i][u.p];

						if(va==1){

							val=time[i][u.p];

						}

						if(val+u.v < meen[i]){

							meen[i]=val+u.v;

							aa.push(state(i,meen[i]));

						}

					}

				}

			}

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

		}

	}

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>

#include<queue>



#define INF 1<<29



using namespace std;



int main(){

	while(1){

		int n,m;

		scanf("%d%d",&m,&n);

		if(m==0 && n==0){

			break;

		}

		int cost[101][101];

		int time[101][101];

		

		for(int i=0;i<101;i++)

		for(int j=0;j<101;j++)

		cost[i][j]=time[i][j]=INF;

		

		for(int i=0;i<m;i++){

			int a,b,c,d;

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

			cost[a][b]=cost[b][a]=c;

			time[a][b]=time[b][a]=d;

		}

		

		for(int k=1;k<=n;k++){

			for(int i=1;i<=n;i++){

				for(int j=1;j<=n;j++){

					cost[i][j]=min(cost[i][j],cost[i][k]+cost[k][j]);

					time[i][j]=min(time[i][j],time[i][k]+time[k][j]);

				}

			}

		}

		

		scanf("%d",&m);

		for(int i=0;i<m;i++){

			int a,b,c;

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

			if(c==0){

				printf("%d\n",cost[a][b]);

			}else{

				printf("%d\n",time[a][b]);

			}

		}

	}

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<vector>

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

using namespace std;



int main(void){

  int n,m;

  while(cin>>n>>m,n+m){

    vector<vector<vector<int> > > dp(2,vector<vector<int> >(100,vector<int>(100,1<<22)));

    rep(i,n){

      int a,b,c,t;

      cin>> a >> b >> c >> t;

      dp[0][--a][--b] = c;

      dp[0][b][a] = c;

      dp[1][a][b] = t;

      dp[1][b][a] = t;

    }

    

    rep(k,m)rep(i,m)rep(j,m)rep(o,2)

      dp[o][i][j] = min(dp[o][i][j],dp[o][i][k]+dp[o][k][j]);

      

    int k;

    cin>>k;

    rep(i,k){

      int p,q,r;

      cin >> p >> q >> r;

      cout<< dp[r][--p][--q] << endl;

    }

  }

}

// Optimized solution to the same problem (faster):
#include<iostream>

using namespace std;

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

int main(void){

  int maze[2][100][100];

  int n,m;

  int a,b,c,t;

  while(cin>>m>>n,n+m){

    rep(i,n)rep(j,n)rep(k,2)maze[k][i][j]=100000;

    rep(i,m){

      cin>>a>>b>>c>>t;

      maze[0][--a][--b]=c;

      maze[1][a][b]=t;

      maze[0][b][a]=c;

      maze[1][b][a]=t;

    }

    rep(k,n)rep(i,n)rep(j,n)rep(l,2)

      maze[l][i][j]=min(maze[l][i][j],maze[l][i][k]+maze[l][k][j]);

    cin>>m;

    //cout<<endl;rep(i,n)rep(j,n)cout<<maze[1][i][j]<<(j==n-1?'\n':' ');

    

    rep(i,m){

      cin>>a>>b>>c;

      cout<<maze[c][--a][--b]<<endl;

    }

  }

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

#include <cstring>

using namespace std;



#define REP(i,k,n) for(int i=k;i<n;++i)

#define rep(i,n) REP(i,0,n)



int N,M,K;

const int MAXN=128;

const int INF=1e+9;

int G1[MAXN][MAXN];

int G2[MAXN][MAXN];



int main()

{

	while(cin>>M>>N&&(M||N))

	{

		rep(i,N){ rep(j,N){ G1[i][j]=G2[i][j]=(i==j?0:INF); } }



		rep(i,M)

		{ 

			int a,b,c,d;

			cin>>a>>b>>c>>d; --a; --b;

			G1[a][b]=G1[b][a]=c;

			G2[a][b]=G2[b][a]=d;

		}



		rep(point,N) rep(from,N) rep(to,N)

		{

			G1[from][to] = min(G1[from][to],G1[from][point]+G1[point][to]);

			G2[from][to] = min(G2[from][to],G2[from][point]+G2[point][to]);

		}



		cin>>K;

		rep(i,K)

		{

			int a,b,c; cin>>a>>b>>c; --a; --b;

			cout<<(c?G2[a][b]:G1[a][b])<<endl;

		}

	}



	return 0;

}

// Optimized solution to the same problem (faster):
#include <stdio.h>

#include <limits.h>

 

int n,m;

 

int Selection(int start,int goal,int Graph[101][101])

{

    int i;

    int min,minp = start;

    int Station[101];

    int Decided[101] = {0,};

 

    for(i=0;i<101;i++)

    {

        Station[i] = INT_MAX;

    }

 

    Station[start] = 0;

 

    while(Decided[goal] == 0)

    {

        for(i=0;i<m+1;i++)

        {

            if(Graph[minp][i] == -1) continue;

 

            if(Station[i] > Graph[minp][i] + Station[minp])

            {

                Station[i] = Graph[minp][i] + Station[minp];

            }

        }

 

        min = INT_MAX;

        for(i=0;i<m+1;i++)

        {

            if(min > Station[i] && Decided[i] != 1)

            {

                min = Station[i];

                minp = i;

            }

        }

        Decided[minp] = 1;

    }

 

    return Station[goal];

}

 

int main()

{

    int Gcost[101][101];

    int Gtime[101][101];

 

    int i,j;

    int a,b,time,cost;

    int k,start,goal,r;

    int ans;

 

    while(1)

    {

        for(i=0;i<101;i++)

        {

            for(j=0;j<101;j++)

            {

                Gcost[i][j] = -1;

                Gtime[i][j] = -1;

            }

        }

 

        scanf("%d%d",&n,&m);

        if(n == 0 && m==0) break;

 

        for(i=0;i<n;i++)

        {

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

            Gcost[a][b] = cost;

            Gcost[b][a] = cost;

            Gtime[a][b] = time;

            Gtime[b][a] = time;

        }

 

        scanf("%d",&k);

        for(i=0;i<k;i++)

        {

            scanf("%d%d%d",&start,&goal,&r);

            if(r==0) ans = Selection(start,goal,Gcost);

            else if(r==1) ans = Selection(start,goal,Gtime);

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

        }

    }

 

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<algorithm>

using namespace std;



int main(){

  int n,m,a,b,cost,time,k,p,q,r;

  int t[100][100],c[100][100];



  for(;;){

    cin >> n >> m;

    if(!n && !m)break;



    for(int i=0;i<m;i++){

      for(int j=0;j<m;j++){

	if(i==j){

	  t[i][j] = 0;

	  c[i][j] = 0;

	}else{

	  t[i][j] = 1000000;

	  c[i][j] = 1000000;

	}

      }

    }



    for(int i=0;i<n;i++){

      cin >> a >> b >> cost >> time;

      t[a-1][b-1] = time;

      t[b-1][a-1] = time;

      c[a-1][b-1] = cost;

      c[b-1][a-1] = cost;

    }



    for(int x=0;x<m;x++){

      for(int i=0;i<m;i++){

	for(int j=0;j<m;j++){

	  t[i][j] = min(t[i][j],t[i][x] + t[x][j]);

	  c[i][j] = min(c[i][j],c[i][x] + c[x][j]);

	}

      }

    }



    cin >> k;

    for(int i=0;i<k;i++){

      cin >> p >> q >> r;

      if(r)cout << t[p-1][q-1] << endl;

      else cout << c[p-1][q-1] << endl;

    }

  }

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>

using namespace std;



int main(){

  int n,m,a,b,cost,time,k,p,q,r;

  int t[100][100],c[100][100];



  for(;;){

    scanf("%d %d",&n,&m);

    if(!n && !m)break;



    for(int i=0;i<m;i++){

      for(int j=0;j<m;j++){

	if(i==j){

	  t[i][j] = 0;

	  c[i][j] = 0;

	}else{

	  t[i][j] = 1000000;

	  c[i][j] = 1000000;

	}

      }

    }



    for(int i=0;i<n;i++){

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

      t[a-1][b-1] = time;

      t[b-1][a-1] = time;

      c[a-1][b-1] = cost;

      c[b-1][a-1] = cost;

    }



    for(int x=0;x<m;x++){

      for(int i=0;i<m;i++){

	for(int j=0;j<m;j++){

	  t[i][j] = min(t[i][j],t[i][x] + t[x][j]);

	  c[i][j] = min(c[i][j],c[i][x] + c[x][j]);

	}

      }

    }



    scanf("%d",&k);

    for(int i=0;i<k;i++){

      scanf("%d %d %d",&p,&q,&r);

      if(r)printf("%d\n",t[p-1][q-1]);

      else printf("%d\n",c[p-1][q-1]);

    }

  }

}

// Fastest known solution for this problem: