CodeForces 756B Travel Card 二分 DP

http://codeforces.com/problemset/problem/756/B

B. Travel Card

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

A new innovative ticketing systems for public transport is introduced in Bytesburg. Now there is a single travel card for all transport. To make a trip a passenger scan his card and then he is charged according to the fare.

The fare is constructed in the following manner. There are three types of tickets:

  1. a ticket for one trip costs 20 byteland rubles,
  2. a ticket for 90 minutes costs 50 byteland rubles,
  3. a ticket for one day (1440 minutes) costs 120 byteland rubles.

Note that a ticket for x minutes activated at time t can be used for trips started in time range from t to t + x - 1, inclusive. Assume that all trips take exactly one minute.

To simplify the choice for the passenger, the system automatically chooses the optimal tickets. After each trip starts, the system analyses all the previous trips and the current trip and chooses a set of tickets for these trips with a minimum total cost. Let the minimum total cost of tickets to cover all trips from the first to the current is a, and the total sum charged before is b. Then the system charges the passenger the sum a - b.

You have to write a program that, for given trips made by a passenger, calculates the sum the passenger is charged after each trip.

Input

The first line of input contains integer number n (1 ≤ n ≤ 105) — the number of trips made by passenger.

Each of the following n lines contains the time of trip ti (0 ≤ ti ≤ 109), measured in minutes from the time of starting the system. All ti are different, given in ascending order, i. e. ti + 1 > ti holds for all 1 ≤ i < n.

Output

Output n integers. For each trip, print the sum the passenger is charged after it.

Examples

input

output

input

output

Note

In the first example, the system works as follows: for the first and second trips it is cheaper to pay for two one-trip tickets, so each time 20 rubles is charged, after the third trip the system understands that it would be cheaper to buy a ticket for 90 minutes. This ticket costs 50 rubles, and the passenger had already paid 40 rubles, so it is necessary to charge 10 rubles only.

题意

有一个乘车的收费系统,出售单次票20元,90分钟票50元,1440分钟票120元。当有人来购票的时候,系统会统计前面已经买票的人,然后让总价格最少的方式,要求现在的人补足差价即可。问每个人需要补多少钱。

样例1的解释,3个人,分别在第10分钟、20分钟、30分钟来乘车。第一个人系统买了单次票,第二个人也是单次票,第三个人,由于前两个人已经一共付了40元,且第一个人和第三个人没有超过90分钟,所有系统选择了90分钟票,所以补了10元。

思路

用dp[i]来表示前i个人最少需要花多少钱。很明显,dp是单调递增的。每次算dp[i]的时候,将买单次票、90分钟票,120分钟票的三种情况分别算出后取最小值即可。对于算90分钟和120分钟的,进行二分查找,找到第一个tp>ti-90(或者120)的人,补差价即可。

 

HDU 5951 Winning an Auction 博弈论DP


http://acm.hdu.edu.cn/showproblem.php?pid=5951

Winning an Auction

Problem Description

Alice and Bob play an auction game. Alice has A dollars and Bob has B dollars initially. There are N items on sale. In each round, an item will be sold by the following way. Alice writes down an integer a (0 ≤ a ≤ A) and Bob writes down an integer b (0 ≤ b ≤ B), which are the amount of dollars they want to pay for the item. If a > b, then Alice gets the item and pays a dollars to the seller. If a < b, then Bob gets the item and pays b dollars to the seller. If a = b, then for the 1st, 3rd, 5th, 7th ... round, Alice gets the item and pays a dollars; for the 2rd, 4th, 6th, 8th ... round, Bob gets the item and pays b dollars. Since all the items have the same value, the goal of the auction game is to get as many items as possible. Both Alice and Bob know the values of N,A and B. Your task is to calculate how many items they will get if both of them play optimally.

Input

The first line is the number of test cases.
Each test case contains 3 integers N,A and B, which are no larger than
255.

Output

For each test case, output the number of items
Alice and Bob will get if both of them play optimally.

Sample Input

3
1 1 2
2 4 2
3 3 3

Sample Output

Alice 0 Bob 1
Alice 1 Bob 1
Alice 2 Bob 1

Source

 
题意
两个人竞拍n个物品,A有a元钱,B有b元钱。出价高的人获得该物品,如果出价相同,奇数轮物品A获得,否则B获得,两人都以最优策略获得尽量多的物品进行竞拍,问最后这两个人各获得了多少物品。
思路
很容易想到一点,如果要放弃这个物品,那么竞拍的时候出价0元就好了。采用到倒推的方法,用dp[o][p][a][b]表示开始的时候是物品的奇偶性(o=1为奇数)为o,剩余p个物品,A有a元钱,B有b元钱,A最多能获得的物品的个数。当A占优势的时候(为奇数轮的时候),假设A出了u元,那么B想要获得这个物品,必须要出u+1的钱,但是如果出了之后,并没有让A的收益变少,就可以舍弃这个物品了(出价0元)。这时,如果B竞拍这个物品成功会使A的收益减少,A就会继续加价,如果加价之后并不会让A的收益变多,那么A就放弃……如此循环下去直到B的钱不够竞拍或者满足上述的要求。B占优势的时候也是类似的。最后预处理一下这个dp就可以了。

 

 

HDU 5981 Guess the number DP决策

http://acm.hdu.edu.cn/showproblem.php?pid=5981


Guess the number

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 160000/160000 K (Java/Others)

Problem Description

AOA just met a problem when he attended an interview, as shown below:
A and B two people play guessing games. A thinks of a number x between a and b randomly in his mind, and he lets B to guess this number. A will say too small if B’s guess is less than x and A will say yes if B’s guess is just x.Once B’sguess is bigger than x,A won't speak any more.After that,A just nods his head if B’s guess is just x,otherwise shakes his head.The problem is that how many kinds of best guess strategies to make the least number of guesses in the worst situation?

Input

Input contains multiple sets of test data and each of them occupies one line,including two integersa, b(1≤a≤b≤5 * 10^6),on behalf of range of the number.Input to the end of the file.

Output

For each set of input, output one line containing two integers. The first one represents the least number of times of guessing in the worst situation. The second one represents the number of best guess method modulo 100000073.

Sample Input

1 5

Sample Output

3 3

Hint

B can guess the number in A's mind up to 3 times in the worst case. The first method,B can guess in the order of (2,4,5) The second method,B can guess in the order of (3,4,5) The third method,B can guess in the order of (3,5) Each method is up to three times.

Source

题意

猜一个[a,b]区间内的数,如果猜小了会被告知小了,相等会被告知对了,但是猜大了之后,只会被告知对还是不对。问最优策略在最坏情况的猜的次数,以及最优策略的方案数。

思路

可以将猜区间[a,b]看作猜区间[1,b-a+1],即长度为b-a+1。设dp[i]猜长度i在最优策略下最坏情况所需的步数,则dp[i] = $min_{j}(max(j-1, dp[i-j]) + 1$,枚举第一次猜的数为j,如果大了,那么就是只能暴力地猜[1,j-1]里面的数,最坏情况就是j-1次,否则就是已最优策略猜后面的i-j个数,步数为dp[i-j],取一个最小值,就是最优策略。可以观察到,当j在一个连续区间[L,R]内,都是最优的决策点,找到L和R,最优策略的方案数就是 $\sum\limits_{j=L}^{R} s[j]$。其中s[j]为长度j的段的最优策略的方案数。维护一下s[i]的前缀和,这个求和就能O(1)算出来了。当i+1的时候,L,R的变化不会很大,暴力一下就好了。

 

 

HDU 5972 Regular Number Bitset优化字符串匹配

http://acm.hdu.edu.cn/showproblem.php?pid=5972


Regular Number

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Problem Description

Using regular expression to define a numeric string is a very common thing. Generally, use the shape as follows:
(0|9|7) (5|6) (2) (4|5)
Above regular expression matches 4 digits:The first is one of 0,9 and 7. The second is one of 5 and 6. The third is 2. And the fourth is one of 4 and 5. The above regular expression can be successfully matched to 0525, but it cannot be matched to 9634.
Now,giving you a regular expression like the above formula,and a long string of numbers,please find out all the substrings of this long string that can be matched to the regular expression.

Input

It contains a set of test data.The first line is a positive integer N (1 ≤ N ≤ 1000),on behalf of the regular representation of the N bit string.In the next N lines,the first integer of the i-th line is $a_i(1 ≤a_i≤ 10)$,representing that the i-th position of regular expression has $a_i$ numbers to be selected.Next there are $a_i$ numeric characters. In the last line,there is a numeric string.The length of the string is not more than 5 * 10^6.

Output

Output all substrings that can be matched by the regular expression. Each substring occupies one line

Sample Input

4
3 0 9 7
2 5 7
2 2 5
2 4 5
09755420524

Sample Output

9755
7554
0524
 

Source
2016ACM/ICPC亚洲区大连站-重现赛(感谢大连海事大学)

题意

给一个长度为n的模式子串,子串的每个位置分别可以是一些数字,即一个位置可以被多个数字匹配。再给定一个母串,问子串可以在哪些位置和母串匹配,并且输出匹配成功后的所有子串。

思路

对每一个数字建立一个bitset,对于每一个数字i的bitset b[i]来说,如果允许他出现在子串的j位置,那么设置b[i][j]=1,否则b[i][j]=0。维护一个bitset ans,枚举母串的每一个位置i,先将ans向高位移一位,再将ans的最低位置1后与这个位置的数字对应的bitset相与。这样,如果ans[k]=1表示从这个位置开始往前的长度为k+1的串可以和子串的前缀进行匹配。当ans[n-1]的时候,说明从i-n+1位置开始的母串可以和子串匹配,这个时候输出即可。由于巨大的io,所以需要加上FastIO才能通过

 

 

HDU 5956 树上进行斜率优化DP + 记录操作并撤销

http://acm.hdu.edu.cn/showproblem.php?pid=5956

The Elder

Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)


Problem Description

Once upon a time, in the mystical continent, there is a frog kingdom, ruled by the oldest frog, the Elder. The kingdom consists of N cities, numbered from east to west. The 1-th city, which is located to the east of others, is the capital. Each city, except the capital, links none or several cities to the west, and exactly one city to the east.
There are some significant news happening in some cities every day. The Elder wants to know them as soon as possible. So, that is the job of journalist frogs, who run faster than any other frog. Once some tremendous news happen in a city, the journalist in that city would take the message and run to the capital. Once it reach another city, it can either continue running, or stop at that city and let another journalist to transport. The journalist frogs are too young and simple to run a long distance efficiently. As a result, it takes $L^2$ time for them to run through a path of length L. In addition, passing message requires P time for checking the message carefully, because any mistake in the message would make the Elder become extremely angry.
Now you are excited to receive the task to calculate the maximum time of sending a message from one of these cities to the capital.

Input

The first line of input contains an integer t, the number of test cases. t test cases follow. For each test case, in the first line there are two integers N (N ≤ 100000) and P (P ≤ 1000000). In the next N-1 lines, the i-th line describes the i-th road, a line with three integers u,v,w denotes an edge between the u-th city and v-th city with length w(w ≤ 100).

Output

For each case, output the maximum time.

Sample Input

3
6 10
1 2 4
2 3 5
1 4 3
4 5 3
5 6 3
6 30
1 2 4
2 3 5
1 4 3
4 5 3
5 6 3
6 50
1 2 4
2 3 5
1 4 3
4 5 3
5 6 3

Sample Output

51
75
81

Hint

In the second case, the best transportation time is: • The 2-th city: 16 = 4^2 • The 3-th city: 72 = 4^2 + 30 + 5^2 • The 4-th city: 9 = 3^2 • The 5-th city: 36 = (3 + 3)^2 • The 6-th city: 75 = (3 + 3)^2 +30 + 3^2 Consequently, the news in the 6-th city requires most time to reach the capital.

Source

题目翻译

从前,在神秘的大陆,有一个青蛙王国,由最年长的青蛙——长者统治着。这个王国由N座城市组成,从东到西编号。第一座城市是首都,座落在最东边。每一个城市,连接者几个或者没有连接几个西边的城市,并且只连接了一个东边的城市。
每天,都有一些大新闻发生在一些城市。长者想尽快地知道。所以,青蛙新闻工作者的工作就是,跑得比其他青蛙都快。当有巨大新闻发生在某座城市的时候,这座城市的新闻工作者将会携带信息,跑向首都。当到达另一个城市的时候,他可以继续跑,也可停下来让其他的新闻工作者传输信息。这些新闻工作者由于太年轻并且简单,不能有效的跑很长的距离。结果,他们需要 $L^2$的时间来跑一条长度为L的路径。除此之外,传达信息需要P的时间,是为了检查传达信息是否有误,因为信息的误差会使长者极度的生气。
现在你高兴的收到一个任务:计算从所有城市发送信息到首都的所需的最长的时间。
 

思路

可以将图看成一个由1点为根的树,每个点到根结点为路径是唯一的。设dp[u]为u点传输信息到根节点的所需时间。a[u]为u点到根节点的距离。很明显,dp[u] = min{dp[k]+$(a[u]-a[k])^2$+P | k是u的祖先)。用斜率优化优化DP转移即可。但是不同的点路径不同,所以这里还需要记录在这个点对于斜率优化的队列操作了什么,回溯离开这个点的时候,需要撤销这些操作,操作每个点有一个栈记录即可。对于从根节点转移吃出来,可以考虑单独转移,也可设置dp[1]=-P
 

 

 

HDU 6004 Periodical Cicadas 中国剩余定理 + 二维RMQ

http://acm.hdu.edu.cn/showproblem.php?pid=6004


Periodical Cicadas

Time Limit: 14000/7000 MS (Java/Others)    Memory Limit: 80000/80000 K (Java/Others)

Problem Description

Nearly all cicadas spend years underground as juveniles, before emerging above ground for a short adult stage of several weeks to a few months.
The seven periodical cicada species are so named because, in any one location, all of the members of the population are developmentally synchronized they emerge as adults all at once every seven years.
The lifecycles of most periodical cicada species range from two to seventeen years, although some could be longer.
There is a forest which can be roughly divided into a matrix of size N ×M. The upper-left region is (1, 1) and the lower-right region is (N, M).
A population of periodical cicadas live within each region of the matrix. The population in region (i, j) emerged in year $a_{i,j}$ for the first time, and re-emerges every $b_{i,j}$ years. i.e. they are $b_{i,j}$ - periodical cicadas.
Given a selected rectangular area, entomologists wonder if there is a time when all cicadas in that area emerge together.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test cases begin with two integers N and M.
The following N lines each consists of M integers $a_{i,j}$ representing the year cicadas emerged in region (i, j) for the first time.
The following N more lines each consists of M integers $b_{i,j}$ representing the periodical cycle of the cicadas in that region.
Then comes a line with an integer Q representing the number of queries. The following Q lines each consists of 4 integers: $x_1, y_1, x_2, y_2,$ representing the upper-left and lower-right coordinate of the selected rectangular area.

 Output

For each test case, first output one line containing “Case #x:”, where x is the test case number (starting from 1).
The following Q lines each consists of an integer which is the year when all cicadas in the selected area emerge together for the first time or -1 if it’s impossible.

limits

$\bullet 1 ≤ T ≤ 10.$
$\bullet 1 ≤ N, M ≤ 200.$
$\bullet 0 ≤ a_{i,j} < b_{i,j} ≤ 40.$
$\bullet 1 ≤ x_1 ≤ x_2 ≤ N.$
$\bullet 1 ≤ y_1 ≤ y_2 ≤ M.$
$\bullet$ 1 ≤ Q ≤ 500000.

Sample Input

2
3 4
3 1 1 2
1 1 2 1
1 0 5 5
5 4 2 3
2 2 3 2
4 2 6 6
5
2 2 2 2
1 1 3 4
1 4 2 4
1 1 1 2
2 2 3 4
1 2
0 1
2 2
1
1 1 1 2

 Sample Output

Case #1:
1
-1
5
13
-1
Case #2:
-1

 Source

 

题意

在一个n*m的矩阵中,每个格子有一只蝉。每只蝉分别会在$ a_{i,j}$ 时间叫一声,然后每$ b_{i,j}$时间叫一声($0 ≤ a_{i,j} < b_{i,j} ≤ 40.$)。有Q次询问,每次询问从$x_1,y_1$到$x_2,y_2$区域内,所有蝉同时叫的最早的时间,如果不会同时叫,输出-1。

思路

可以把每个蝉看作同余方程,即$t_{i,j} \equiv  a_{i,j}(\mod b_{i,j} )$,每只蝉会在$t_{i,j}$时间叫,询问一个区域的时候,将区域内的所有同余方程用中国剩余定理合并即可。由于重复合并相同的方程不会对结果造成影响,可以使用二维RMQ来预处理区域内的同余方程。要注意在合并方程的时候,会出现乘法超出long long数据范围的问题。

 

HDU5957 Query on a graph 基环树 + BFS序列 + 线段树区间维护

http://acm.hdu.edu.cn/showproblem.php?pid=5957

Query on a graph

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Problem Description

You are given a connected simple graph(in which both multiple edges and loops are disallowed) with N nodes and N edges. In this graph each node has a weight, and each edge has the same length of one unit. Define D(u,v) as the distance between node u and node v. Define S(u,k) as the set of nodes x which satisfy D(u,x) ≤ k.
We will ask you to perform some instructions of the following forms.
MODIFY u k d: weight of all nodes in S(u,k) increase by d or decrease by -d.
QUERY u k: ask for the sum of weight of all nodes in S(u,k).
In the beginning, the weight of all nodes are 0.

Input

The first line of input contains an integer t, the number of test cases. t test cases follow. For each test case, in the first line there is an integer N(N ≤ 100000). The i-th line of the next N line describes the i-th edge: two integers u,v denotes an edge between u and v. In the next line, an integer Q(Q ≤ 100000) indicates the number of instructions. Next Q lines contain instructions MODIFY u k d or QUERY u k, where |d|≤ 100 and 0 ≤ k ≤ 2.

Output

For each QUERY instruction, output a integer in a line.

Sample Input

2
6
1 2
2 3
3 4
4 1
4 5
3 6
5
MODIFY 1 1 3
MODIFY 3 1 2
MODIFY 5 2 1
QUERY 3 2
QUERY 4 1
6
1
2 2
3 3
1 1
4 2
5 3
6 5
MODIFY 3 1 5
MODIFY 2 2 2
QUERY 6 1
MODIFY 4 1 -2
QUERY 2 2

Sample Output

21
14
14
28

Source

题意

给一个n个点n条边的无向联通图(n <=10w),边权都是1。定义集合d(u,k)为距离 u点不超过k的点集合。有q次操作或者询问(q<=10w),每次操作是吧d(u,k)集合内的点点权加上d,询问是询问d(u,k)集合内所有的点权和。(0<=d<=2)

思路

对于上诉的图,名字叫做基环树。存在一个环,环上的每一个点都是一个树的根。先将这个环找到。这样问题就从图上的询问简化到了树上。由于是询问或者操作一个范围,可以考虑使用BFS序。维护每一个节点他的儿子和孙子的BFS序的最大值和最小值,同一个树的所有儿子的BFS序一定是连续的,孙子的BFS也一定是连续的,对于这个范围操作,可以考虑使用线段树来进行维护。当k=0的时候,就是单点操作,k=1的时候,先操作u的所有儿子和u点,如果u点在环上,还要单点操作u在环上的周围的两个点。当k=2的时候,情况就比较复杂的。情况1:u点在环上,先操作单点u点和u的儿子以及u的孙子,在环上距离u点为1的两个点x,对x进行单点操作,并对x的儿子进行操作,在环上距离u点为2的两个点y,对y进行单点操作。但是要注意环大小为3的时候和4的时候,操作会重复,需要减去多余操作。情况2:u不在环上,先操作单点u点和u的儿子以及u的孙子,再单点操作u的父亲fa,操作fa的儿子,这时候,u点背重复操作,所以前面一次对u的操作可以不做。这时,如果fa在环上,单点操作fa在环上周围的两个点,否则单点操作fa的父亲。
 

 

 

Codeforces158E Dividing Kingdom 暴力枚举 + 可持久化线段树

E. Dividing Kingdom

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

A country called Flatland is an infinite two-dimensional plane. Flatland has n cities, each of them is a point on the plane.

Flatland is ruled by king Circle IV. Circle IV has 9 sons. He wants to give each of his sons part of Flatland to rule. For that, he wants to draw four distinct straight lines, such that two of them are parallel to the Ox axis, and two others are parallel to the Oy axis. At that, no straight line can go through any city. Thus, Flatland will be divided into 9 parts, and each son will be given exactly one of these parts. Circle IV thought a little, evaluated his sons' obedience and decided that the i-th son should get the part of Flatland that has exactly aicities.

Help Circle find such four straight lines that if we divide Flatland into 9 parts by these lines, the resulting parts can be given to the sons so that son number i got the part of Flatland which contains ai cities.

Input

The first line contains integer n (9 ≤ n ≤ 105) — the number of cities in Flatland. Next n lines each contain two space-separated integers: xi, yi ( - 109 ≤ xi, yi ≤ 109) — the coordinates of the i-th city. No two cities are located at the same point. The last line contains nine space-separated integers: .

Output

If there is no solution, print a single integer -1.

Otherwise, print in the first line two distinct real space-separated numbers: x1, x2 — the abscissas of the straight lines that are parallel to the Oy axis. And in the second line print two distinct real space-separated numbers: y1, y2 — the ordinates of the straight lines, parallel to the Ox. If there are multiple solutions, print any of them.

When the answer is being checked, a city is considered to lie on a straight line, if the distance between the city and the line doesn't exceed 10 - 6. Two straight lines are considered the same if the distance between them doesn't exceed 10 - 6.

Examples

input

output

input

output

input

output

Note

The solution for the first sample test is shown below:

The solution for the second sample test is shown below:

There is no solution for the third sample test.

题意:

将平面用两条垂直于x轴的直线和两条垂直与y轴的直线划分成如图所示的九个区域,要求每个区域内的点为一定的数目(顺序随意),问这四条直线的坐标。如果不能输出-1。

思路:

先将点离散化,再插入按y值建树的可持久化线段树,每个x值一棵树。这样就可以快速的查一个矩形区域内的点的个数。然后暴力全排列枚举每个区域内点的个数。再用建好的可持久化线段树检查即可。具体方法是根据枚举的区域内的点的个数,可以知道垂直于x轴分出的三个区域内点的个数,这样就可以确定直线的x值,再这样确定两个y值。再分别检查划分出的区域内的点是否和枚举的相同。如果相同,就可以输出了。

 

 

Codeforces 754C Vladik and chat 字符串处理+DP

http://codeforces.com/problemset/problem/754/C

C. Vladik and chat

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Recently Vladik discovered a new entertainment — coding bots for social networks. He would like to use machine learning in his bots so now he want to prepare some learning data for them.

At first, he need to download t chats. Vladik coded a script which should have downloaded the chats, however, something went wrong. In particular, some of the messages have no information of their sender. It is known that if a person sends several messages in a row, they all are merged into a single message. It means that there could not be two or more messages in a row with the same sender. Moreover, a sender never mention himself in his messages.

Vladik wants to recover senders of all the messages so that each two neighboring messages will have different senders and no sender will mention himself in his messages.

He has no idea of how to do this, and asks you for help. Help Vladik to recover senders in each of the chats!

Input

The first line contains single integer t (1 ≤ t ≤ 10) — the number of chats. The t chats follow. Each chat is given in the following format.

The first line of each chat description contains single integer n (1 ≤ n ≤ 100) — the number of users in the chat.

The next line contains n space-separated distinct usernames. Each username consists of lowercase and uppercase English letters and digits. The usernames can't start with a digit. Two usernames are different even if they differ only with letters' case. The length of username is positive and doesn't exceed 10 characters.

The next line contains single integer m (1 ≤ m ≤ 100) — the number of messages in the chat. The next m line contain the messages in the following formats, one per line:

  • <username>:<text> — the format of a message with known sender. The username should appear in the list of usernames of the chat.
  • <?>:<text> — the format of a message with unknown sender.

The text of a message can consist of lowercase and uppercase English letter, digits, characters '.' (dot), ',' (comma), '!' (exclamation mark), '?' (question mark) and ' ' (space). The text doesn't contain trailing spaces. The length of the text is positive and doesn't exceed 100 characters.

We say that a text mention a user if his username appears in the text as a word. In other words, the username appears in a such a position that the two characters before and after its appearance either do not exist or are not English letters or digits. For example, the text "Vasya, masha13 and Kate!" can mention users "Vasya", "masha13", "and" and "Kate", but not "masha".

It is guaranteed that in each chat no known sender mention himself in his messages and there are no two neighboring messages with the same known sender.

Output

Print the information about the t chats in the following format:

If it is not possible to recover senders, print single line "Impossible" for this chat. Otherwise print m messages in the following format:

<username>:<text>

If there are multiple answers, print any of them.

Examples

Input

Output

Input

Output

Input

Output

 题意:

给一段聊天记录,每条形如<username>:<text>或者<?>:<text>。其中<username>代表发出这条消息的人,<?>代表发消息的人未知。发话内容是由一些由逗号、句号、感叹号、问号和空格隔开的单词,并且每个人发话的单词中,不包含自己的名字。问给定的所有发话人的名单后,能不能将<?>确定下来。

思路:

先将每条记录处理出能发出这条记录的人,当然,已经确定<username>的就只有一个人,否则就是所有的未出现在这条消息中的单词的人。然后用dp[i][j]表示第i条记录由第j个人发出是否可行。记录一下dp的前驱,最后输出即可。

 

 

Codeforces 754E Dasha and cyclic table bitset优化矩阵匹配

http://codeforces.com/problemset/problem/754/E

E. Dasha and cyclic table

time limit per test

6 seconds

memory limit per test

512 megabytes

input

standard input

output

standard output

Dasha is fond of challenging puzzles: Rubik's Cube 3 × 3 × 3, 4 × 4 × 4, 5 × 5 × 5 and so on. This time she has a cyclic table of size n × m, and each cell of the table contains a lowercase English letter. Each cell has coordinates (i, j) (0 ≤ i < n, 0 ≤ j < m). The table is cyclic means that to the right of cell (i, j) there is the cell , and to the down there is the cell .

Dasha has a pattern as well. A pattern is a non-cyclic table of size r × c. Each cell is either a lowercase English letter or a question mark. Each cell has coordinates (i, j) (0 ≤ i < r, 0 ≤ j < c).

The goal of the puzzle is to find all the appearance positions of the pattern in the cyclic table.

We say that the cell (i, j) of cyclic table is an appearance position, if for every pair (x, y) such that 0 ≤ x < r and 0 ≤ y < c one of the following conditions holds:

  • There is a question mark in the cell (x, y) of the pattern, or
  • The cell of the cyclic table equals to the cell (x, y) of the pattern.

Dasha solved this puzzle in no time, as well as all the others she ever tried. Can you solve it?.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 400) — the cyclic table sizes.

Each of the next n lines contains a string of m lowercase English characters — the description of the cyclic table.

The next line contains two integers r and c (1 ≤ r, c ≤ 400) — the sizes of the pattern.

Each of the next r lines contains a string of c lowercase English letter and/or characters '?' — the description of the pattern.

Output

Print n lines. Each of the n lines should contain m characters. Each of the characters should equal '0' or '1'.

The j-th character of the i-th (0-indexed) line should be equal to '1', in case the cell (i, j) is an appearance position, otherwise it should be equal to '0'.

Examples

Input

Output

Input

Output

Input

Output

题意:

给定一个n*m的字母矩阵,这个矩阵在x和y方向都周期性延拓。在给定一个r*c的矩阵,其中?代表通配符。输出一个n*m的01矩阵,代表r*c的矩阵可以和n*m的矩阵在这个位置匹配上。

思路:

对于每一个1,是以这个点为左上角的r*c的矩阵的每一个格子是否匹配的逻辑与。用G[c][i][j]表示n*m矩阵的(i,j)位置是否是c,换句话说,如果G[c][i][j]=1,表示c可以在(i,j)位置可以和n*m的矩阵匹配上。将最后一个压成bitset。枚举r*c矩阵的每一个格子,再枚举这个格子出现n*m矩阵的哪一排。然后将G[rc[i][j]][i]怼到bitset ans[x-i]上面,表示这一排和rc[i][j]的匹配情况。最后将ans输出即可。