#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
//using namespace atcoder;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define mydeb(fmt, ...) fprintf(stderr, fmt, __VA_ARGS__)
//#define mydeb(fmt, ...) 

int main()
{
    int64_t k,n,m;
    cin >> k >> n >> m;
    vector<int64_t> a(k);
    rep(i,k)
    {
        cin >> a[i];
    }

    vector<int64_t> modn(k);
    int64_t modtotal=0;
    rep(i,k)
    {
        modn[i]=(a[i]*m)%n;
        modtotal+=modn[i];
        //mydeb("i:%d modn:%ld\n",i,modn[i]);
    }
    modtotal/=n;

    vector<pair<int,int>> mp(k);
    rep(i,k)
    {
        mp[i]=make_pair(modn[i],i);
    }
    sort(mp.begin(),mp.end());

    auto it=mp.rbegin();
    vector<int> add1(k);
    rep(i,modtotal)
    {
        add1[it->second]=1;
        ++it;
    }

    bool first=true;
    rep(i,k)
    {
        if (first==false)
        {
            cout << " ";
        }
        first=false;
        cout << a[i]*m/n + add1[i];
    }
}

#include<bits/stdc++.h>
#define rep(i,n) for(int i = 0 ; i < (n); ++i)
using namespace std ;
using ll=long long ;
using P=pair<ll,int> ;

const int mod=1000000007;
const int N=1e5 ;
const ll INF=1e18;

struct Edge
{	
	int to,t,k ;
	Edge(int to, int t ,int k):to(to),t(t),k(k){}
	
};

void solve(){

int n,m,s,d ;
cin>>n>>m>>s>>d ;

s-- ;
d-- ;

vector<vector<Edge>> g(n+1) ;

rep(i,m){

	int a,b,t,k ;
	cin>>a>>b>>t>>k ;
	a-- ;
	b-- ;
	g[a].emplace_back(b,t,k) ;
	g[b].emplace_back(a,t,k) ;

}

vector<ll> dist(n,INF) ;

priority_queue<P,vector<P>,greater<P>> q ;

auto push=[&](int v,ll x){
	if(dist[v]<=x) return ;
	dist[v]=x ;
	q.emplace(x,v) ;

};

push(s,0) ;

while(!q.empty()){

	auto x=q.top().first ;
	auto v=q.top().second ;

	q.pop() ;
	if(dist[v]!=x)	continue ;

	for(Edge &e:g[v]){
		ll nx=((x+e.k-1)/e.k)*e.k+e.t ;
		push(e.to,nx) ;
	}
}

if(dist[d]==INF)
	cout<<-1 ;
else
	cout<<dist[d] ;


}	

int main(){
 
	#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin) ;
		freopen("output.txt","w",stdout) ;
    #endif 

		cin.tie(0);
		cout.tie(0);
		ios_base::sync_with_stdio(false);  

		int y ;

		y=1 ;
		//cin>>y ;

		while(y--){
 
			solve() ;
			
		}

		return 0 ;
}