Description

Last Pokemon Contest (神奇寶貝華麗大賽) between Satoshi (小智) and Haruka (小遙) ! After Satoshi won the victory in Battle Pyramid, Satoshi and Haruka signed up for an unofficial Pokemon Contest in Terracotta Town.

Pokemon Contest is a contest in which trainers and Pokemons coordinate strength and beauty. It is divided into two stages. In the first stage, the Performance Stage, trainers and their Pokemons will perform moves to showcase their styles and skills. In the second stage, the Battle Stage, trainers battles against each other as well as demonstrating charm of their Pokemons.

Satoshi and Haruka met in the Battle stage, where Satoshi's Sceptile (蜥蜴王) fought against Haruka's Blaziken (火焰雞). In the final ten seconds of the battle, Haruka's Blaziken activates Blaze (猛火) and fires Overheat (過熱). To battle in a dazzling style, the pattern of Overheat is cleverly designed with golden ratio:

The pattern of Overheat can be expressed with a string. First, Haruka and Blaziken design two short patterns F0 and F1. Then they generate longer patterns using the following recurrence formula: Fn-2 + Fn-1 = Fn (+ means string concatenation). Finally, Haruka tells Blaziken a number n, and Blaziken fires the Overheat with pattern Fn.

Given F0, F1, n, and k, please find out the k-th character in Fn.

For full episode, please google "AG191 Satoshi vs. Haruka! Last Battle!!" or refer to this page.

Explanation on Sample IO

All test data provide same F0 = "abc", F1 = "def". We can generate the following patterns:

• F2 = "abcdef"

• F3 = "defabcdef"

• F4 = "abcdefdefabcdef"

The first test data asks 0-th character of F0, therefore output 'a'. Similarly, the outputs for the second to fifth test data are 'd', 'f', 'f', 'e', respectively.

Input

The input contains multiple test data. The first line of input contains an integer T, being number of test data. After that are T test data.

The first line of test data contains two non-empty strings F0 and F1.

The second line of test data contains two integers n and k.

• 1 <= T <= 100

• F0 and F1 contain only lower case alphabets (a-z) and have length no greater than 2000.

• 0 <= n < 60 and 0 <= k < |Fn|, where |Fn| is length of Fn

Output

For each test data, output the answer in a single line.  Remember to add new line in the end.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

After escaping the Magical Corridor, you realize your ordeal is far from over—there’s a second challenge, and KenKenKen’s relentless pursuit continues.

This time, however, his curse has weakened. The restriction on your bag—limiting you to carrying only one gem of each color—has vanished!

Now, you can collect as many gems of any color as you wish, but your objective remains unchanged:

• For a given position m, collect the maximum number of distinct gem colors possible.
• Among all collections with the maximum distinct colors, maximize the total weight of the gems you collect.

The magical movement rules are still in effect:

• If you are at position i, you can only move to positions that are multiples of i. For example, if you are at position 1, you can move to positions 2,3,…,N. From position 2, you can only move to positions 4,6,…

Can you use this newfound freedom to outsmart KenKenKen and finally escape? Your cunning and strategy will decide your fate.

Input

The first line contains two integers N and Q, the length of the corridor and the number of queries.

The second line contains N integers C₁,C₂,...,C_N , where C_i represents the color of the gem at position i.

The third line contains N integers W₁,W₂,...,W_N , where W_i represents the weight of the gem at position i.

The next Q lines each contain a single integer m, specifying the endpoint for each query.

Constraints

• 1 ≤ N,Q ≤ 10⁵
• 1 ≤ C_i ≤ 7
• 1 ≤ W_i ≤ 10⁵
• 1 ≤ m ≤ N

Subtasks

• Testcases 1~2: N,Q ≤ 10
• Testcases 3~4: N,Q ≤ 10²
• Testcases 5~6: N ≤ 10⁴ , Q = 1
• Testcases 7~8: Q = 1
• Testcases 9~10: No additional restrictions.

Output

For each query, output two integers in a single line:

1. The maximum number of distinct gem colors you can collect up to position m.
2. The maximum total weight of the gems you can collect, with the maximum number of distinct gem colors, up to position m.

Please remember to print "\n" at the end of each line.

Sample Input  Download

Sample Output  Download

Tags

Discuss