Original problem statement (in Polish) can be found here.

The annual Congress of Mages is approaching. Januarius the Clairvoyant intends to participate in it. He has to somehow reach the city where the convention takes place.

His favourite means of transportation is railway. He plans to travel using a convenient, direct connection. The train will visit n stations, numbered with consecutive integers. It will depart from station number 1, with station number n as its destination. Remaining stations are intermediate - the train will visit them in order, according to their numbers.

Januarius likes travelling by train for a lot of reasons - it's comfortable, you can admire the landscape in peace - but most importantly, tickets are quite cheap. National Railways determined that cost of the trip depends only on the number of sections between stations covered during the ride. Ticket for i sections costs w_i. Obviously, the prices become higher when the trip gets longer.

You could also travel without a ticket if you're feeling adventurous, but of course there is a risk of unexpected ticket inspection, which can happen during the ride between two consecutive stations. Life of the clairvoyant is devoid of any surprises though - Januarius knows exactly when there will be an inspection. He doesn't have to buy full ticket - it's only important to have valid ticket during the inspection (starting station can be any station before the inspection, and the destination can be any station after the inspection).

There are two ways to buy a ticket - from the ticket office at the station, or already on the train, from the ticket inspector. There are limitations though. If you board the train without a ticket, you have to find the inspector immediately after the departure. He only sells tickets starting from the station you boarded the train at. Also, if you boarded the train at the station with a ticket office, you have to pay an additional constant fee of d.

Januarius has no time to get off the train during the ride, so he can either buy the ticket at the first station in a ticket office, or at any station from the inspector (he can approach him immediately after the departure from the station and tell him he just boarded the train).

Find the cheapest ticket-buying strategy. You must have a valid ticket during every inspection.

Input

The first line contains a single integer t, denoting the number of testcases. Then, descriptions of the testcases follow.

First line of the description consists of three integers n, k and d - number of stations, number of inspections and an additional fee for buying a ticket from the inspector in case there is a ticket office at the station (1 <= n <= 10⁶, 1 <= k <= 1000, 1 <= d <= 10⁹).

In the second line there is a string of length n. If station number i has a ticket office, i-th character of this string is "1", otherwise it's "0".

In the third line there are n-1 integers. i-th number w_i denotes price of covering i sections. (1 <= w_i <= 10⁹, w_i < w_i+1).

In the last line there are k integers s_i - stations numbers. i-th ticket inspection will take place between the station number s_i and the station number s_i+1. (1 <= s_i <= n-1, s_i < s_i+1)

Output

For every testcase you should output a ticket-buying strategy that minimizes total cost. Description of the strategy starts with two integers s and b - total cost of the tickets and number of tickets (1 <= b <= n). Descriptions of the tickets should follow. One ticket description consists of two integers p_i and c_i - starting station and number of segments for which the ticket is valid. (1 <= p_i < n, 1 <= c_i <= n-p_i).

You should describe b tickets, their total cost must be equal to s, and it has to be minimal.

Example

Input:

1
5 2 5
11001
2 6 7 10
2 4

Output:

8 2
1 2
4 1

Explanation

There are two inspections - between stations 2 and 3, and between stations 4 and 5. Januarius can buy a ticket in the ticket office from the station number 1 to the station number 3, and another one from the inspector from station number 4 to station number 5, and it will cost him 6+2=8.

If he bought the first ticket from the second station instead from the first, it would be more expensive - there is a ticket office at the second station, so there will be an additional fee for buying the ticket from the inspector. (2+5+2=9).