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

#define MP make_pair
#define PB push_back
#define ALL(x)      (x).begin(),(x).end()
#define REP(i,n)    for(int i=0;i<(n);i++)
#define REP1(i,n)   for(int i=1;i<(n);i++)
#define REP2(i,d,n) for(int i=(d);i<(n);i++)
#define RREP(i,n)   for(int i=(n);i>=0;i--)
#define CLR(a)      memset((a),0,sizeof(a))
#define MCLR(a)     memset((a),-1,sizeof(a))
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI > VVI;
typedef vector<string> VS;
typedef vector<LL> VLL;
typedef pair<int,int> PII;

const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;

const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};

int main(){
    LL N;
    cin >> N;
    VI P(N);
    VI P_index(N);

    REP(i, N) {
        cin >> P[i];
        P[i]--;
        P_index[P[i]] = i;
    }

    set<int> swap_idx;
    VI ans;
    REP(i, N-1) {
        while(i != P_index[i]) {
            int prev_num = P[P_index[i]-1];
            if (swap_idx.count(P_index[i])) {
                cout << -1 << endl;
                return 0;
            }

            swap_idx.insert(P_index[i]);
            ans.PB(P_index[i]);
            swap(P[P_index[i]], P[P_index[i]-1]);
            swap(P_index[i], P_index[prev_num]);
        }
    }

    if (swap_idx.size() == N-1) {
        REP(i, ans.size()) {
            cout << ans[i] << endl;
        }
    } else {
        cout << -1 << endl;
    }
}

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

#define INF 9999999999999999
template<class T>
bool chmin(T& a,T b)
{
    if(a > b)
    {
	a = b;
	return true;
    }
    else
    {
	return false;
    }
}

struct Edge
{
    long long to;
    long long weight;
    long long time;
};

long long calc(long long nowminute,long long time)
{
    if(nowminute % time == 0) return nowminute;
    else return(nowminute + time - nowminute % time);
}

using Graph = vector<vector<Edge>>;
using P = pair<long long,long long>;
int main()
{
    long long N,M,X,Y;
    cin >> N >> M >> X >> Y;
    X--; Y--;
    Graph G(N);
    vector<long long> dp(N);
    vector<bool> kakutei(N);
    for(long long i = 0;i < M;i++)
    {
        long long tmpa,tmpb,tmpt,tmpk;
        cin >> tmpa >> tmpb >> tmpt >> tmpk;
        tmpa--; tmpb--;
        Edge tmpedge1,tmpedge2;
        tmpedge1.to = tmpb;
        tmpedge2.to = tmpa;
        tmpedge1.weight = tmpedge2.weight = tmpt;
        tmpedge1.time = tmpedge2.time = tmpk;
        G[tmpa].push_back(tmpedge1);
        G[tmpb].push_back(tmpedge2);
    }
    priority_queue<P,vector<P>,greater<P>> PQ;
    kakutei.assign(N,false);
    dp.assign(N,INF);
    dp[X] = 0;
    PQ.push(make_pair(0,X));
    while(!PQ.empty())
    {
        auto tmppair = PQ.top();
        PQ.pop();
        if(kakutei[tmppair.second]) continue;
        kakutei[tmppair.second] = true;
        for(auto nextedge : G[tmppair.second])
        {
            if(kakutei[nextedge.to]) continue;
            if(chmin(dp[nextedge.to],calc(dp[tmppair.second],nextedge.time)+nextedge.weight))
            {
                PQ.push(make_pair(dp[nextedge.to],nextedge.to));
            }
        }
    }
    if(dp[Y] == INF) cout << -1 << endl;
    else cout << dp[Y] << endl;
}
 
