github.com/captn3m0/codechef.git

---
category_name: medium
problem_code: PATTMATC
problem_name: 'Pattern matching'
languages_supported:
    - ADA
    - ASM
    - BASH
    - BF
    - C
    - 'C99 strict'
    - CAML
    - CLOJ
    - CLPS
    - 'CPP 4.3.2'
    - 'CPP 4.9.2'
    - CPP14
    - CS2
    - D
    - ERL
    - FORT
    - FS
    - GO
    - HASK
    - ICK
    - ICON
    - JAVA
    - JS
    - 'LISP clisp'
    - 'LISP sbcl'
    - LUA
    - NEM
    - NICE
    - NODEJS
    - 'PAS fpc'
    - 'PAS gpc'
    - PERL
    - PERL6
    - PHP
    - PIKE
    - PRLG
    - PYPY
    - PYTH
    - 'PYTH 3.4'
    - RUBY
    - SCALA
    - 'SCM chicken'
    - 'SCM guile'
    - 'SCM qobi'
    - ST
    - TCL
    - TEXT
    - WSPC
max_timelimit: '2'
source_sizelimit: '50000'
problem_author: xcwgf666
problem_tester: logic_iu
date_added: 24-08-2015
tags:
    - kmp
    - ltime28
    - medium
    - pattern
    - string
    - xcwgf666
editorial_url: 'http://discuss.codechef.com/problems/PATTMATC'
time:
    view_start_date: 1440923400
    submit_start_date: 1440923400
    visible_start_date: 1440923400
    end_date: 1735669800
    current: 1493557845
layout: problem
---
All submissions for this problem are available.###  Read problems statements in [Mandarin Chinese](http://www.codechef.com/download/translated/LTIME28/mandarin/PATTMATC.pdf) , [Russian](http://www.codechef.com/download/translated/LTIME28/russian/PATTMATC.pdf) and [Vietnamese](http://www.codechef.com/download/translated/LTIME28/vietnamese/PATTMATC.pdf)

You are given a string **S**, made of lowercase Latin letters.

You are also given a _wildcard_ string **T**, containing lowercase latin letters and asterisks (symbol \*).

Both the strings are 1-indexed.

_Wildcard_ string **T** is said to _generate_ a string **P** if and only if **P** can be obtained from **T** by replacing **all** the asterisks with arbitrary (possibly empty) lowercase Latin letter strings.

Consider the **i**th symbol of the string **S**. Let's calculate the smallest index **pi ≥ i** such that the substring **Si**...**Spi** contains at least one of the strings generated by _wildcard_ string **T**. In case any such index **pi** doesn't exist, then **pi = -1**.

Your goal is to calculate all the values **p1**, **p2**, ... , **p|S|**.

### Input

The first line of input contains an integer **Tn** denoting the number of test cases. The description of **Tn** test cases follows.

The first line of each test case contains a _wildcard_ string **T**.

The second line of the test case contains a lowercase Latin string **S**.

### Output

For each test case, output a single line containing **|S|** space-separated integers, denoting **p1**, **p2**, ..., **p|S|**.

### Constraints

- **1** ≤ **T** ≤ **102**
- Subtask 1 (33 points) : **1** ≤ sum of all **|S|**, sum of all **|T|** over a single test case ≤ **103**, **1** ≤ **|S|**, **|T|** ≤ **102**
- Subtask 2 (33 points) : **1** ≤ sum of all **|S|**, sum of all **|T|** over a single test case ≤ **105**, **1** ≤ **|S|**, **|T|** ≤ **103**
- Subtask 3 (34 points) : **1** ≤ sum of all **|S|**, sum of all **|T|** over a single test case ≤ **105**, **1** ≤ **|S|**, **|T|** ≤ **105**
- Total number of asterisks over all the test cases is at most **500**.

### Example

<pre><b>Input:</b>
<tt>2
*a*
abacaba
*a*b*
abacaba</tt>

<b>Output:</b>
<tt>1 3 3 5 5 7 7
2 6 6 6 6 -1 -1</tt>
</pre>### Explanation

**Example case 1.** Let us show that for every index **i** the value of **pi** is correct:

- **p1** = 1. The corresponding substring **a** contains the string **a**. String **a** can be generated by replacing both asterisks with empty strings.
- **p2** = 3. The corresponding substring **ba** contains the string **a**.
- **p3** = 3. The corresponding substring **a** contains the string **a**.
- **p4** = 5. The corresponding substring **ca** contains the string **ca**. The string **ca** can be obtained if we replace the first asterisk with **c** and the second one with an empty string.
- **p5** = 5. The corresponding substring **a** contains the string **a**.
- **p6** = 7. The corresponding substring **ba** contains the string **ba**. The string **ba** can be obtained if we replace the first asterisk with **b** and the second one with an empty string.
- **p7** = 7. The corresponding substring **a** contains the string **a**.

**Example case 2.** Again, let's check for every **i**.

- **p1** = 2. The corresponding substring **ab** contains **ab**. The string **ab** can be obtained if we replace all the asterisks with empty strings.
- **p2** = 6. The corresponding substring **bacab** contains **acab**. The string **acab** can be obtained if we replace the first asterisk with an empty string, the second one with the string **ca** and the third one with an empty string.
- **p3** = 6. The corresponding substring **acab** contains **ab**.
- **p4** = 6. The corresponding substring **cab** contains **cab**. The string **cab** can be obtained if you replace the first asterisk with **c**, and the rest with empty strings.
- **p5** = 6. The corresponding substring **ab** contains **ab**.
- **p6** = **p7** = -1. Neither **ba** nor **a** doesn't contain any substring, generated by \*a\*b\*.

You may have noted that in the explanation for the second test case, **ab** is also a correct substring generated by **T** for some positions, but some other string is listed. This is done on purpose, in order to show how the string **T** can generate various strings.