stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <bits/stdc++.h>



using namespace std;



int main(){

  	int n, x;

  	vector<int> nums, sortNums;

  

  	cin >> n;	

  

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

    	cin >> x;

      	nums.push_back(x);

    }

  	

  	sortNums = nums;

  	sort(sortNums.begin(), sortNums.begin()+n);

  

    if(nums == sortNums){

      cout << "YES\n";

      return 0;

    } 

  

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

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

    		swap(nums[i],nums[j]);

        	if(nums == sortNums){

              	cout << "YES\n";

              	return 0;

            } 

          	swap(nums[i],nums[j]);

        }

    }

  

  	cout << "NO\n";

  

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.138605726169861x):
#include<stdio.h>



int main()



{

   int i,j,tc,a[100000],cnt=0,z;



   scanf("%d",&tc);



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

   {

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

   }



   for(j=1,z=0;j<=tc;j++,z++)

   {

      if(j!=a[z])

      {

         cnt++;

      }

   }



   if(cnt<=2)

   {

      printf("YES\n");

   }



   else

   {

      printf("NO\n");

   }

}
// Slower C++ solution:


#include <bits/stdc++.h>



using namespace std;

  

bool checkingAlgo(int koyta, int seq[]) 

{  

    int duplicate[koyta]; 

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

        duplicate[i] = seq[i]; 

    sort(duplicate, duplicate + koyta); 

  

 

    int swap = 0; 

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

        if (seq[i] != duplicate[i]) 

            swap++; 

    if (swap == 0 || swap == 2) 

        return true; 

    else

        return false; 

} 

  



int main() 

{   

    int koyta;

    cin >> koyta;



    int seq[koyta]; 

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

        cin >> seq[i]; 

     



    if (checkingAlgo(koyta, seq)) 

        cout << "YES"; 

    else

        cout << "NO"; 

    return 0; 

} 


// Faster C++ solution for the same problem (measured speedup: 5.084939723184712x):
#include<stdio.h>



int main()



{

   int i,j,tc,a[100000],cnt=0,z;



   scanf("%d",&tc);



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

   {

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

   }



   for(j=1,z=0;j<=tc;j++,z++)

   {

      if(j!=a[z])

      {

         cnt++;

      }

   }



   if(cnt<=2)

   {

      printf("YES\n");

   }



   else

   {

      printf("NO\n");

   }

}
// Slower C++ solution:
#include <iostream>

#include <string>

#include <algorithm>



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

#define e '\n'

#define ll long long int



#define ii InputInteger()

#define il InputLong()

#define is InputString()



using namespace std;



void Ia(int arr[], int n)

{

    f

    {

        cin >> arr[i];

    }

}

void Pa(int arr[], int n)

{

    f

    {

        cout << arr[i] << e;

    }

}

int InputInteger()

{

    int n;

    cin >> n;

    return n;

}

ll InputLong()

{

	ll n;

	cin >> n;

	return n;

}

string InputString()

{

	string s;

	cin >> s;

	return s;

}

void Ca(int arr[], int n)

{

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

    {

        arr[ i ] = 0;

    }

}

int main()

{

    ios_base::sync_with_stdio( false );



        int n = ii, p = 0;

        int a[n], s[n];

        Ia(a, n);

        f

        {

            s[i] = a[i];

        }

        sort(s, s+n);

        f

        {

            if(a[i] != s[i]) p++;

        }

       if (p>2) cout << "NO";

       else cout << "YES";



    return 0;

}






// Faster C++ solution for the same problem (measured speedup: 5.18972498407221x):
#include<stdio.h>



int main()



{

   int i,j,tc,a[100000],cnt=0,z;



   scanf("%d",&tc);



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

   {

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

   }



   for(j=1,z=0;j<=tc;j++,z++)

   {

      if(j!=a[z])

      {

         cnt++;

      }

   }



   if(cnt<=2)

   {

      printf("YES\n");

   }



   else

   {

      printf("NO\n");

   }

}
// Slower C++ solution:
/*  TAHMID RAHMAN

    DAMIAN FOREVER

     MATH LOVER

    NEVER GIVE UP

*/

#include<bits/stdc++.h>

using namespace std;

#define pi acos(-1.0)

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

#define ll long long

#define pb push_back

#define fi first

#define se second

#define in insert

#define mp make_pair

#define GCD(a,b) __gcd(a,b);

#define endl "\n"

#define FRU freopen("out.txt","w",stdout)

#define FRO freopen("in.txt","r",stdin)

#define INFLL 9223372036854775807

#define debug 0

#define MAXN   100001

#define ar array

const int mxN=2e5;

const int MOD=1e9+7;

bool sortbysec(const pair<int,int> &a,const pair<int,int> &b){return (a.second < b.second);}

//Don't hesitate to ask me if you don't understand my code.......Happy coding,Tahmid...;

int main()

{



    ll n,i;

    cin>>n;

    vector<ll>v(n);

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

    {

        cin>>v[i];

    }

    set<ll>s;

    vector<ll>a(v.begin(),v.end());

    sort(a.begin(),a.end());

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

    {

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

        {

            s.in(a[i]);

            s.in(v[i]);

        }

    }

    if(s.size()==0||s.size()==2)

    {

        cout<<"YES"<<endl;

    }

    else

        cout<<"NO"<<endl;



}


// Faster C++ solution for the same problem (measured speedup: 5.14502748571479x):
#include<stdio.h>



int main()



{

   int i,j,tc,a[100000],cnt=0,z;



   scanf("%d",&tc);



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

   {

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

   }



   for(j=1,z=0;j<=tc;j++,z++)

   {

      if(j!=a[z])

      {

         cnt++;

      }

   }



   if(cnt<=2)

   {

      printf("YES\n");

   }



   else

   {

      printf("NO\n");

   }

}
// Slower C++ solution:
#include<iostream>

using namespace std;

#include<bits/stdc++.h>

#define PI			2*acos(0.0)

int main()

{

    int n,i;

    cin >>n;

    int a[n+1],c=0,y1,y2=0;

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

    {

        cin >>a[i];

        if(a[i]!=i)

        {

            if(c==0)

            {

                c++;

                y1=i;

            }

            else if(c==1)

            {

                c++;

                if(a[i]==y1)

                {

                    y2=1;

                }

            }

            

        }

    }

    if(c==2&&y2==1)

    {

        cout <<"YES";

    }

    else if(c==0)

    {

        cout <<"YES";

    }

    else

        cout <<"NO";

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.081412788553912x):
#include<stdio.h>



int main()



{

   int i,j,tc,a[100000],cnt=0,z;



   scanf("%d",&tc);



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

   {

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

   }



   for(j=1,z=0;j<=tc;j++,z++)

   {

      if(j!=a[z])

      {

         cnt++;

      }

   }



   if(cnt<=2)

   {

      printf("YES\n");

   }



   else

   {

      printf("NO\n");

   }

}
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 5.08036053736407x):
#include<stdio.h>



int main()



{

   int i,j,tc,a[100000],cnt=0,z;



   scanf("%d",&tc);



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

   {

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

   }



   for(j=1,z=0;j<=tc;j++,z++)

   {

      if(j!=a[z])

      {

         cnt++;

      }

   }



   if(cnt<=2)

   {

      printf("YES\n");

   }



   else

   {

      printf("NO\n");

   }

}
// Slower C++ solution:
#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;

}




// Faster C++ solution for the same problem (measured speedup: 5.083456454390121x):
#include<stdio.h>



int main()



{

   int i,j,tc,a[100000],cnt=0,z;



   scanf("%d",&tc);



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

   {

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

   }



   for(j=1,z=0;j<=tc;j++,z++)

   {

      if(j!=a[z])

      {

         cnt++;

      }

   }



   if(cnt<=2)

   {

      printf("YES\n");

   }



   else

   {

      printf("NO\n");

   }

}
// Slower C++ solution:
#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;

}







}


// Faster C++ solution for the same problem (measured speedup: 5.093652522398106x):
#include<stdio.h>



int main()



{

   int i,j,tc,a[100000],cnt=0,z;



   scanf("%d",&tc);



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

   {

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

   }



   for(j=1,z=0;j<=tc;j++,z++)

   {

      if(j!=a[z])

      {

         cnt++;

      }

   }



   if(cnt<=2)

   {

      printf("YES\n");

   }



   else

   {

      printf("NO\n");

   }

}
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 5.092806583281731x):
#include<stdio.h>



int main()



{

   int i,j,tc,a[100000],cnt=0,z;



   scanf("%d",&tc);



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

   {

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

   }



   for(j=1,z=0;j<=tc;j++,z++)

   {

      if(j!=a[z])

      {

         cnt++;

      }

   }



   if(cnt<=2)

   {

      printf("YES\n");

   }



   else

   {

      printf("NO\n");

   }

}
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 5.08561338902979x):
#include<stdio.h>



int main()



{

   int i,j,tc,a[100000],cnt=0,z;



   scanf("%d",&tc);



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

   {

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

   }



   for(j=1,z=0;j<=tc;j++,z++)

   {

      if(j!=a[z])

      {

         cnt++;

      }

   }



   if(cnt<=2)

   {

      printf("YES\n");

   }



   else

   {

      printf("NO\n");

   }

}
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 5.082120914869363x):
#include<stdio.h>



int main()



{

   int i,j,tc,a[100000],cnt=0,z;



   scanf("%d",&tc);



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

   {

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

   }



   for(j=1,z=0;j<=tc;j++,z++)

   {

      if(j!=a[z])

      {

         cnt++;

      }

   }



   if(cnt<=2)

   {

      printf("YES\n");

   }



   else

   {

      printf("NO\n");

   }

}
// Slower C++ solution:
#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";

}

// Faster C++ solution for the same problem (measured speedup: 5.090305465606539x):
#include<stdio.h>



int main()



{

   int i,j,tc,a[100000],cnt=0,z;



   scanf("%d",&tc);



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

   {

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

   }



   for(j=1,z=0;j<=tc;j++,z++)

   {

      if(j!=a[z])

      {

         cnt++;

      }

   }



   if(cnt<=2)

   {

      printf("YES\n");

   }



   else

   {

      printf("NO\n");

   }

}
// Slower C++ solution:
//  ©   ___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;

}


// Faster C++ solution for the same problem (measured speedup: 5.128074301078047x):
#include<stdio.h>



int main()



{

   int i,j,tc,a[100000],cnt=0,z;



   scanf("%d",&tc);



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

   {

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

   }



   for(j=1,z=0;j<=tc;j++,z++)

   {

      if(j!=a[z])

      {

         cnt++;

      }

   }



   if(cnt<=2)

   {

      printf("YES\n");

   }



   else

   {

      printf("NO\n");

   }

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 5.251360899639787x):
#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;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 5.228710009707371x):
#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);

}
// Slower C++ solution:
#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;

} 

// Faster C++ solution for the same problem (measured speedup: 5.117289393411918x):
#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]);

		}

	}

}
// Slower C++ solution:
#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;

} 

// Faster C++ solution for the same problem (measured speedup: 5.117289393411918x):
#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]);

		}

	}

}
// Slower C++ solution:
#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;

} 

// Faster C++ solution for the same problem (measured speedup: 3.594023345852441x):
#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]);

			}

		}

	}

}