#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 7;
int x[MAXN], st[MAXN][18];
int main()
{
    int n; scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &x[i]);
    int L, Q; scanf("%d%d", &L, &Q);
    // memset(st, 0x3f3f3f3f, sizeof(st));
    for (int i = 1; i <= n; i++)
        st[i][0] = min(n, (int)(upper_bound(x + 1, x + 1 + n, x[i] + L) - x - 1));

    
    for (int j = 1; j < 18; j++)
        for (int i = 1; i <= n; i++)
            st[i][j] = st[st[i][j - 1]][j - 1];
    while (Q--)
    {
        int l, r; scanf("%d%d", &l, &r);
        if (l > r) swap(l, r);
        int res = 0;
        for (int j = 17; j >= 0; j--)
            if (st[l][j] < r) res += (1 << j), l = st[l][j];
        printf("%d\n", res + 1);
    }
    return 0;
}
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <string>
#include <cstring>
#include <set>
#include <vector>
#include <map>
using namespace std;

typedef long long LL;
	
const LL INF = 0x7ffffffff;
const LL NBDR = -2e7;
const LL BDR = 2e7;
const LL MAXN = 200;
LL G[MAXN][MAXN];

LL n, k, u, v, w;


void init()
{
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			G[i][j] = i == j ? 0 : INF;
}

void floyd()
{
	for(int k = 0; k < n; k++)
	{
		for(int i = 0; i < n; i++)
		{
			if(G[i][k] == INF)
				continue; 
			for(int j = 0; j < n; j++)
			{
				if(G[k][j] == INF)
					continue;
				G[i][j] = min(G[i][j], G[i][k] + G[k][j]);	
			}
		}
			
	}		
}


int main()
{
	while(scanf("%lld %lld", &n, &k) != EOF)
	{
		init();
		int flag = 0;
		while(k--)
		{
			scanf("%lld %lld %lld", &u, &v, &w);
			G[u][v] = w;
		}
		
		floyd();
		
		for(int i = 0; i < n; i++)
			if(G[i][i] < 0)
			{
				printf("NEGATIVE CYCLE\n");
				flag = 1;
				break;
			}
				
		if(flag == 1)
			continue;		
				 
		for(int i = 0; i < n; i++)
		{
			for(int j = 0; j < n; j++)
			{
				if(G[i][j] == INF && j < n-1)
					printf("INF ");
				else if(G[i][j] == INF && j < n)
					printf("INF");
				else if(G[i][j] != INF && j < n-1)
					printf("%lld ", G[i][j]);
				else if(G[i][j] != INF && j < n)
					printf("%lld", G[i][j]);
			}
			printf("\n");
		}
	}


	return  0;
}

