Tara and Sandy are at the beach! Tara is showing Sandy a card trick with each card labeled with a single, not necessarily unique, lowercase English character.

Initially, Tara has a sequence of cards ~s_1, s_2, \ldots, s_k~ and shows it to Sandy. Tara then performs a cyclic shift on the cards (a cyclic shift is obtained by repeatedly moving cards from the front of the sequence to the back). For example, the cyclic shifts of abcde are abcde, bcdea, cdeab, deabc, and eabcd. Let this new sequence of cards be ~p_1, p_2, \ldots, p_k~.

Afterwards, Tara takes a completely random sequence of card(s) ~a_1, a_2 \ldots, a_n~ from a seperate deck and inserts it in front of the sequence ~p~. The then takes another random sequence of card(s) ~b_1, b_2, \ldots, b_m~ and places it behind the sequence ~p~ (it is possible for sequence ~a~ and/or ~b~ to be empty). The final sequence is ~a_1, a_2, \ldots, a_n, p_1, p_2, \ldots, p_k, b_1, b_2, \ldots, b_m~. Let's call this sequence ~h~.

Sandy saw Tara perform these steps but suspects that Tara performed some sort of sleight of hand. Given the original sequence ~s_1, s_2, \ldots, s_k~, and Tara's proposed sequence for ~h~, determine the possible ways to achieve this proposed sequence ~h~ from ~s~ though the above operations.

Constraints

Note: ~|x|~ denotes the length of the sequence ~x~.

In all test cases, ~1 \le |s| \le |h| \le 3.5 \times 10^5~

Subtask 1 [20%]

~|s| \le |h| \le 4000~

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line contains the sequence ~s_1, s_2, \ldots, s_k~ (the original sequence of cards).

The second line contains Tara's proposed sequence ~h~.

Output Specification

If it is possible to convert ~s~ into Tara's proposed ~h~ sequence through these operations, list all the ~1~-indices that sequence ~p~ can begin on in increasing order. Otherwise, output -1.

Sample Input 1

abcde
cazbcdeatueabcde

Output for Sample Case 1

4
11
12

Explanation for Sample Case 1

There are ~3~ ways for Tara to generate ~h~:

1. Generate the cyclic shift bcdea, prepend caz, and append tueabcde to create the resulting sequence. The sequence ~p~ (bcdea) begins on the ~4^{th}~ character of sequence ~h~.
2. Generate the cyclic shift eabcd, prepend cazbcdeatu, and append e to create the resulting sequence. The sequence ~p~ (eabcd) begins on the ~11^{th}~ character of sequence ~h~.
3. Generate the cyclic shift abcde, prepend cazbcdeatue, and append nothing to create the resulting sequence. The sequence ~p~ (abcde) begins on the ~12^{th}~ character of sequence ~h~.

Sample Input 2

abcde
wwwvvabcd

Output for Sample Case 2

-1