J. Jugando Fuerte
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

The billionaire explorer Granza, founder of the major space travel company Space-Y, enjoys exploring the Universe aboard his ship, the StarPuma-GTE.

During one of his trips through the Sombrero Galaxy, Granza discovered a planet called Guadalajara. This planet was famous not only for its breathtaking landscapes but also for its enormous casinos and a peculiar card game known as At-Poker.

At-Poker was considered the national pastime of Guadalajara, involving skill, luck, and strategy. On this planet, the casinos are luminous temples where fortunes are made and lost in a matter of rounds. Granza, always a man of challenges, couldn't resist the temptation to participate. As they say in Guadalajara, Granza "jugó fuerte" — he bet high — and unfortunately, his Earth poker skills were of little use against the complex strategies of At-Poker, and he soon found himself without a large part of his fortune.

In At-Poker, $$$N$$$ players numbered from $$$1$$$ to $$$N$$$ are arranged around a circular table in the order $$$1, 2, 3...N$$$, so that for every player $$$i$$$ from $$$1$$$ to $$$N-1$$$, they are to the left of player $$$i+1$$$, and player $$$N$$$ is to the left of player $$$1$$$.

In the game of At-Poker, each player receives a deck of cards represented by a string of lowercase letters and a number $$$G_i$$$. The official rulebook specifies the following:

Rules of At-Poker

  1. Forming the Hand: Each player $$$i$$$ forms their hand by concatenating the decks of the $$$G_i$$$ players to their left, plus their own deck. This is done in a circular manner, where $$$N$$$ is the total number of players. For example, if $$$N = 5$$$ and $$$G_i = 3$$$ for player $$$i = 3$$$, then player 3's hand is formed by concatenating the decks of players $$$5$$$, $$$1$$$, $$$2$$$, and $$$3$$$, in that order.

  2. Wildcards and Scores: There are several strings placed on the table, which are called wildcards. Each wildcard string $$$j$$$ has an associated value $$$X_j$$$.

  3. Calculating the Score: A player's score is determined by the highest value among the wildcards that occur in their hand as a contiguous subsequence, where the occurrence of the wildcard must end within the player's original deck (i.e., it cannot be entirely within the decks of players to their left). If no wildcard occurs in the player's hand, their score is zero.

Determined not to leave Guadalajara as a loser, Granza set out to learn the strategies of At-Poker. He knew that the only way to return to Earth having recovered his losses would be if he could guarantee a win. To do so, he needed a system that could predict, based on the initial hands of each player, how many points each would score at the end of a round.

Input

The first line of input contains an integer $$$N$$$ $$$(1 \leq N \leq 10^5)$$$, representing the number of players at the table.

The next $$$N$$$ lines describe each player. The $$$i$$$-th line contains a string $$$s_i$$$ $$$(1 \leq |s_i| \leq 10^5)$$$ of lowercase letters (from "a" to "z") and an integer $$$G_i$$$ $$$(0 \leq G_i \leq N-1)$$$. The string $$$s_i$$$ represents player $$$i$$$'s deck, and the integer $$$G_i$$$ indicates how many decks of players to their left are used to form their hand.

The following line contains an integer $$$M$$$ $$$(1 \leq M \leq 10^5)$$$, indicating the number of wildcards available on the table.

The next $$$M$$$ lines list the wildcards. The $$$i$$$-th line contains a string $$$t_i$$$ $$$(1 \leq |t_i| \leq 10^5)$$$ and an integer $$$X_i$$$ $$$(1 \leq X_i \leq 10^9)$$$. The string $$$t_i$$$ is the pattern to look for in the players' hands, and the integer $$$X_i$$$ is the score assigned to this pattern if it is found in a player's hand, ending within their original deck.

It is guaranteed that the sum of the lengths of the strings $$$s_i$$$ and the sum of the lengths of the strings $$$t_i$$$ do not exceed $$$10^5$$$.

Output

The output must consist of a single line containing $$$N$$$ integers separated by spaces, where the $$$i$$$-th value is the score of player $$$i$$$ in the game.

Examples
Input
3
abd 0
dcbca 0
dbbca 0
3
ab 3
dc 7
c 5
Output
3 7 5
Input
5
adui 0
aba 0
gbcaffdf 0
abfh 0
abbfcafd 0
8
bfc 5
fd 4
ab 7
daduia 16
bagbc 12
bca 1
i 2
fh 10
Output
2 7 4 10 7
Input
5
adui 2
aba 2
gbcaffdf 1
abfh 0
abbfcafd 3
8
bfc 5
fd 4
ab 7
daduia 16
bagbc 12
bca 1
i 2
fh 10
Output
2 16 12 10 7