Manter uma rede de internet de fibra em funcionamento é uma tarefa muito difícil. Diversos fatores afetam o tempo de resposta de comunicação da rede e cada vez mais fica difícil descobrir o melhor caminho que um pacote pode percorrer, ainda mais que os switches podem fazer parte de empresas diferentes, e os custos de passar um pacote seu por ela pode custar mais caro.

Por isso que na vida real as operadoras tentam não usar a rede das concorrentes para trafegar pacotes. Por exemplo, se você usa internet da NET/CLARO e vai se conectar ao youtube, a sua conexão nunca vai passar por roteadores da VIVO. Pois a VIVO cobraria uma taxa de tráfego de empresa externa, quase que como um pedágio de pacotes.

Para resolver este problema, uma notória equipe de desenvolvedores criou o CAI FORA LAG, uma ferramenta que entende como a rede funciona e sempre descobre o menor caminho (e mais barato) para trafegar os pacotes, isso a qualquer momento da rede.

Para garantir uma economia maior, a CAI FORA LAG ainda instalou um sistema chamado SUPER CONEXÃO, que nada mais é que um super switch (muito caro) com um link muito grande que conecta dois pontos de conexão a uma latência baixa e a um custo muuuito baixo, garantindo assim, uma economia nos gastos da empresa e uma melhora no desempenho da rede dos clientes (essencialmente serve apenas para a CAI FORA LAG economizar dinheiro ao ficar roteando os pacotes dos clientes).

O pessoal do CAI FORA LAG precisa encontrar mais parceiros para conseguir colocar em prática a instalação da SUPER CONEXÃO. E, por isso, precisa saber quanto está economizando ao utilizar este método em lugares específicos.

No desenho abaixo temos uma representação de um pedaço da rede, bem simples, que mostra que as conexões entre os nós da rede de fibra (note que não há direção, pois a rede vai e volta) com um custo associado nas arestas, percebemos que o caminho direto do vértice $0$ para $1$ é de $8$.

Temos também, na figura, uma rede de SUPER CONEXÃO ligando os vértices $3$ para $1$ a um custo de $-2$, note que esta conexão é direcionada, ou seja, pacotes podem ser enviados de $3$ para $1$ diretamente, mas o caminho inverso não ocorre.

Então, no desenho acima, se eu quiser enviar um pacote do vértice $0$ para o vértice $2$, o custo sem SUPER CONEXÃO é $7$, passando por 0 - 3 - 2 e quando se considera a existência da SUPER CONEXÃO o custo passa a ser $3$ pois o pacote seguiria o caminho 0 - 3 - 1 -2.

Enviar um pacote de $1$ para $0$ o custo é o mesmo sem e com a SUPER CONEXÃO, pois não há vantagens em se utilizar alguma rota que passe pela SUPER CONEXÃO.

A sua tarefa é descobrir o menor custo de operação de envio de pacotes de uma origem a um destino sem considerar a existência dos nós SUPER CONEXÃO e depois considerando a existência deles.

Entrada

A entrada é composta por um único caso de teste. A primeira linha, do caso de teste, possui um número inteiro $V$ ($2 \leq V \leq 2000$) representando a quantidade de switches (vértices) que foram nomeadas de $0$ a $V$.

A partir da segunda linha, cada linha é composta por quatro inteiros $v$, $w$, $c$ e $t$ ($0 \leq v,w < V$, $-1000 \leq c \leq 1000$, $0 \leq t \leq 1$), com $v$ e $w$ informando a conexão de fibra entre $v$ e $w$, $c$ sendo o custo de se utilizar este caminho e $t$ representando o tipo da conexão $0$ para bidirecional e $1$ para SUPER CONEXÃO que é direcional (não existindo o caminho $w$ $v$ com mesmo custo).

Quando $v=w=c=t=0$, representa que o fim da descrição das conexões e iniciam-se as perguntas da rede.

Para as perguntas cada linha é composta por dois inteiros $o$ e $x$ ($0 \leq o,x < V$) representando a pergunta de qual é o custo para enviar um pacote de $o$ para $x$.

A entrada termina em EOF.

É garantido que ao menos uma aresta e uma pergunta faça parte da entrada.

Saída

Para cada pergunta você deve imprimir uma única linha contendo:

• Dois inteiros $X$ e $S$, sendo $X$ o custo de enviar pacotes de $o$ para $x$ SEM utilizar a super conexão e $S$ sendo o custo de se enviar pacotes utilizando a SUPER CONEXÃO
• Impossibru, quando for impossível calcular o custo com ou sem a SUPER CONEXÃO

Exemplos

Exemplo de Entrada

4
0 1 8 0
0 3 4 0
1 2 1 0
3 2 3 0
3 1 -2 1
0 0 0 0
0 2
1 0
2 1

Saída para o exemplo acima

7 3
8 8
1 1

Exemplo de Entrada

4
0 1 8 0
0 3 4 0
1 2 1 0
3 2 3 0
3 1 -2 1
2 0 -5 1
0 0 0 0
0 2
1 0
2 1

Saída para o exemplo acima

Impossibru
Impossibru
Impossibru

Exemplo de Entrada

4
0 1 8 0
0 3 4 0
1 2 1 0
3 2 3 0
3 1 -2 1
0 2 -5 1
0 0 0 0
0 2
1 0
2 1

Saída para o exemplo acima

7 -5
8 8
1 1

Exemplo de Entrada

5
0 1 8 0
0 3 4 0
1 2 1 0
3 2 3 0
3 1 -2 1
0 0 0 0
0 2
0 4

Saída para o exemplo acima

7 3
Impossibru

Exemplo de Entrada

10
6 3 820 0
6 1 270 0
1 0 160 0
9 0 489 0
3 4 574 0
2 1 28 0
8 9 368 0
8 7 138 0
7 5 30 0
2 8 313 0
6 7 153 0
7 1 272 0
4 7 182 0
9 2 369 0
9 5 80 0
5 8 877 0
2 6 689 0
7 9 219 0
8 1 334 0
4 2 453 0
2 3 86 0
0 5 239 0
7 0 245 0
5 2 314 0
3 7 324 0
4 8 164 0
8 6 897 0
5 3 371 0
2 0 280 0
0 0 0 0
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
1 0
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
2 0
2 1
2 3
2 4
2 5
2 6
2 7
2 8
2 9
3 0
3 1
3 2
3 4
3 5
3 6
3 7
3 8
3 9
4 0
4 1
4 2
4 3
4 5
4 6
4 7
4 8
4 9
5 0
5 1
5 2
5 3
5 4
5 6
5 7
5 8
5 9
6 0
6 1
6 2
6 3
6 4
6 5
6 7
6 8
6 9
7 0
7 1
7 2
7 3
7 4
7 5
7 6
7 8
7 9
8 0
8 1
8 2
8 3
8 4
8 5
8 6
8 7
8 9
9 0
9 1
9 2
9 3
9 4
9 5
9 6
9 7
9 8

Saída para o exemplo acima

160 160
188 188
274 274
427 427
239 239
398 398
245 245
383 383
319 319
160 160
28 28
114 114
454 454
302 302
270 270
272 272
334 334
382 382
188 188
28 28
86 86
453 453
314 314
298 298
300 300
313 313
369 369
274 274
114 114
86 86
506 506
354 354
384 384
324 324
399 399
434 434
427 427
454 454
453 453
506 506
212 212
335 335
182 182
164 164
292 292
239 239
302 302
314 314
354 354
212 212
183 183
30 30
168 168
80 80
398 398
270 270
298 298
384 384
335 335
183 183
153 153
291 291
263 263
245 245
272 272
300 300
324 324
182 182
30 30
153 153
138 138
110 110
383 383
334 334
313 313
399 399
164 164
168 168
291 291
138 138
248 248
319 319
382 382
369 369
434 434
292 292
80 80
263 263
110 110
248 248

Exemplo de Entrada

18
15 7 -938 1
11 0 600 0
13 14 587 0
0 15 274 0
9 6 885 0
12 17 925 0
10 13 40 0
1 5 49 0
13 4 247 0
5 6 78 0
11 12 84 0
1 15 742 0
12 4 962 0
4 9 528 0
17 16 14 0
8 5 120 0
11 1 943 0
7 14 767 0
2 17 673 0
2 14 399 0
11 17 923 0
13 6 587 0
10 5 348 0
0 2 557 0
11 13 793 0
7 3 59 0
6 15 660 0
11 16 596 0
7 6 39 0
14 15 0 0
7 10 87 0
7 8 651 0
14 11 230 0
9 11 944 0
17 15 369 0
12 0 98 0
13 2 956 0
4 16 839 0
13 3 940 0
4 14 222 0
1 14 784 0
15 2 548 0
7 4 869 0
16 3 263 0
11 2 174 0
3 4 582 0
17 8 140 0
15 16 380 0
12 13 582 0
0 1 950 0
1 13 566 0
8 10 37 0
10 9 492 0
14 10 316 0
13 0 327 0
7 17 673 0
11 4 263 0
7 13 19 0
16 6 994 0
16 2 707 0
17 6 310 0
16 8 529 0
12 3 659 0
0 0 0 0
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 10
0 11
0 12
0 13
0 14
0 15
0 16
0 17
1 0
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
2 0
2 1
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 13
2 14
2 15
2 16
2 17
3 0
3 1
3 2
3 4
3 5
3 6
3 7
3 8
3 9
3 10
3 11
3 12
3 13
3 14
3 15
3 16
3 17
4 0
4 1
4 2
4 3
4 5
4 6
4 7
4 8
4 9
4 10
4 11
4 12
4 13
4 14
4 15
4 16
4 17
5 0
5 1
5 2
5 3
5 4
5 6
5 7
5 8
5 9
5 10
5 11
5 12
5 13
5 14
5 15
5 16
5 17
6 0
6 1
6 2
6 3
6 4
6 5
6 7
6 8
6 9
6 10
6 11
6 12
6 13
6 14
6 15
6 16
6 17
7 0
7 1
7 2
7 3
7 4
7 5
7 6
7 8
7 9
7 10
7 11
7 12
7 13
7 14
7 15
7 16
7 17
8 0
8 1
8 2
8 3
8 4
8 5
8 6
8 7
8 9
8 10
8 11
8 12
8 13
8 14
8 15
8 16
8 17
9 0
9 1
9 2
9 3
9 4
9 5
9 6
9 7
9 8
9 10
9 11
9 12
9 13
9 14
9 15
9 16
9 17
10 0
10 1
10 2
10 3
10 4
10 5
10 6
10 7
10 8
10 9
10 11
10 12
10 13
10 14
10 15
10 16
10 17
11 0
11 1
11 2
11 3
11 4
11 5
11 6
11 7
11 8
11 9
11 10
11 12
11 13
11 14
11 15
11 16
11 17
12 0
12 1
12 2
12 3
12 4
12 5
12 6
12 7
12 8
12 9
12 10
12 11
12 13
12 14
12 15
12 16
12 17
13 0
13 1
13 2
13 3
13 4
13 5
13 6
13 7
13 8
13 9
13 10
13 11
13 12
13 14
13 15
13 16
13 17
14 0
14 1
14 2
14 3
14 4
14 5
14 6
14 7
14 8
14 9
14 10
14 11
14 12
14 13
14 15
14 16
14 17
15 0
15 1
15 2
15 3
15 4
15 5
15 6
15 7
15 8
15 9
15 10
15 11
15 12
15 13
15 14
15 16
15 17
16 0
16 1
16 2
16 3
16 4
16 5
16 6
16 7
16 8
16 9
16 10
16 11
16 12
16 13
16 14
16 15
16 17
17 0
17 1
17 2
17 3
17 4
17 5
17 6
17 7
17 8
17 9
17 10
17 11
17 12
17 13
17 14
17 15
17 16

Saída para o exemplo acima

Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru
Impossibru