Structure of Balanced Networks

Time limit5sMemory limit16 MB

Summary
Given a complete signed graph where every triad is balanced, answer queries about the sign of the edge between two nodes.
Level

Medium5 of 10

Topics
Graph, Math, Union-find, Implementation
Solved
No attempts yet

Problem

Structure of Balanced Networks means that in a Complete Signed Graph (a graph in which an edge exists between every pair of nodes and each edge has a sign), every ① triad is ② balanced. Each term is defined as follows.

  1. triad: the triangle formed by choosing any three nodes in the graph
  2. balance: the states (a) and (c) in the figure below

  1. Every relation is +, so everyone is friends; this is balanced.
  2. B and C have a common friend A. In this case A reconciles B and C (which changes the state to (a)) or B and C alienate each other from A (which changes the state to (c)).
  3. A and B have a common enemy C, which is balanced.
  4. The relations are -, but they form a temporary alliance to deal with the person the three dislike most (which changes the state to (c)).

The following are examples of balanced and unbalanced states.

No relation is one-sided. In other words, the relation between A and B is the relation between B and A.

Given a Structure of Balanced Networks and several pairs of nodes B and C, write a program that prints the sign of the relation between B and C for each query.

Input

The first line gives the number of nodes n (3 ≤ n ≤ 5000).

The next n lines give the relations between the n nodes, one line per node. The j-th character of the (i+1)-th line is '+' for a friend, '-' for an enemy, and '0' for the node itself.

The next line gives the number of queries m (1 ≤ m ≤ 100).

The next m lines give the number b (0 ≤ b < n) of node B and the number c (0 ≤ c < n) of node C.

Each node is represented by a number from 0 to n-1, and B and C are given as different node numbers.

Output

Print the relation between B and C over m lines.

Examples1

  1. Example 1

    Input
    4
0 - - +
- 0 + -
- + 0 -
+ - - 0
2
0 3
3 2
    Expected output
    +
-