BT 13042018

Thu gom rác

OLP2016

Để cải thiện môi trường nhằm thu hút khách du lịch chính quyền của một thành phố du lịch nổi tiếng quyết định tiến hành thu gom và xử lý rác dọc bờ biển. Toàn bộ bờ biển thuộc khu du lịch được chia thành n đoạn đánh số từ 1 đến n. Khảo sát cho thấy ở đoạn thứ i có xi tấn rác, i = 1 ÷ n. Xe liên hợp kiểu mới thu gom, phân loại và chế biến rác được đưa ra vận hành thử nghiệm. Trong một khoảng thời gian hoạt động liên tục xe có thể thu gom và chế biến không quá t tấn rác. Vì là lần vận hành thử nghiệm nên các kỹ sư chế tạo rất thận trọng, muốn chọn một khúc bờ biển nào đó gồm một số đoạn liên tiếp để tiện theo dõi và đánh giá. Hãy xác định có bao nhiêu cách chọn khác nhau nếu chỉ dựa vào tiêu chí đảm bảo sao cho xe không phải xử lý quá t tấn rác. Mỗi đoạn trong khúc đã chọn phải được làm sạch, tức là thu gom hết rác trong đoạn đó. Hai khúc gọi là khác nhau nếu tồn tại một đoạn có ở trong khúc này và không có trong khúc kia.

Dữ liệu:
Vào từ file văn bản TRASH.INP: Dòng đầu tiên chứa 2 số nguyên n và t ( 1 ≤ n ≤ 1e6, 1 ≤ t ≤ 1e9), Dòng thứ 2 chứa n số nguyên x1, x2, . . ., xn (1 ≤ xi ≤ 1e6, i = 1 ÷ n). Tổng các xi không vượt quá 1e9.

Kết quả:
Đưa ra file văn bản TRASH.OUT một số nguyên – số cách lựa chọn khác nhau có thể thực hiện

VD:
Input:
9 10
11 1 2 1 1 5 10 2 3

Ouput:
19

Giải thuật Dijkstra sử dụng cấu trúc dữ liệu Set của C++

Giải thuật Dijkstra sử dụng cấu trúc dữ liệu Set của C++

Input:

Dòng đầu chứa 2 số nguyên n và m.

Dòng thứ i trong m dòng tiếp chứa 3 số nguyên x, y, z thể hiện có đường 2 chiều từ x đến y mang trọng số là z.

Dòng tiếp theo có chứa 1 số nguyên s là đỉnh nguồn

Output:

In ra n số nguyên, số nguyên thứ i thể hiện tổng đường đi ngắn nhất từ s đến đỉnh i.

One-dimensional Japanese Crossword

One-dimensional Japanese Crossword

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Recently Adaltik discovered japanese crosswords. Japanese crossword is a picture, represented as a table sized a × b squares, and each square is colored white or black. There are integers to the left of the rows and to the top of the columns, encrypting the corresponding row or column. The number of integers represents how many groups of black squares there are in corresponding row or column, and the integers themselves represents the number of consecutive black squares in corresponding group (you can find more detailed explanation in Wikipedia https://en.wikipedia.org/wiki/Japanese_crossword).

Adaltik decided that the general case of japanese crossword is too complicated and drew a row consisting of n squares (e.g. japanese crossword sized 1 × n), which he wants to encrypt in the same way as in japanese crossword.

The example of encrypting of a single row of japanese crossword.

Help Adaltik find the numbers encrypting the row he drew.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 100) — the length of the row. The second line of the input contains a single string consisting of n characters 'B' or 'W', ('B' corresponds to black square, 'W' — to white square in the row that Adaltik drew).

Output

The first line should contain a single integer k — the number of integers encrypting the row, e.g. the number of groups of black squares in the row.

The second line should contain k integers, encrypting the row, e.g. corresponding to sizes of groups of consecutive black squares in the order from left to right.

Examples

input

3
BBW

output

1
2 

input

5
BWBWB

output

3
1 1 1 

input

4
WWWW

output

0

input

4
BBBB

output

1
4 

input

13
WBBBBWWBWBBBW

output

3
4 1 3 

Note

The last sample case correspond to the picture in the statement.

Bài làm

The Monster

The Monster

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

A monster is chasing after Rick and Morty on another planet. They're so frightened that sometimes they scream. More accurately, Rick screams at times b, b + a, b + 2a, b + 3a, ... and Morty screams at times d, d + c, d + 2c, d + 3c, ....

The Monster will catch them if at any point they scream at the same time, so it wants to know when it will catch them (the first time they scream at the same time) or that they will never scream at the same time.

Input

The first line of input contains two integers a and b (1 ≤ a, b ≤ 100).

The second line contains two integers c and d (1 ≤ c, d ≤ 100).

Output

Print the first time Rick and Morty will scream at the same time, or  - 1 if they will never scream at the same time.

Examples

input

20 2
9 19

output

82

input

2 1
16 12

output

-1

Note

In the first sample testcase, Rick's 5th scream and Morty's 8th time are at time 82.

In the second sample testcase, all Rick's screams will be at odd times and Morty's will be at even times, so they will never scream at the same time.

Problem: http://codeforces.com/problemset/problem/787/A

Solution: http://codeforces.com/contest/787/submission/25752856