Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

combinatorics

data structures

math

*2100

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Monocarp and the Set

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputMonocarp has $$$n$$$ numbers $$$1, 2, \dots, n$$$ and a set (initially empty). He adds his numbers to this set $$$n$$$ times in some order. During each step, he adds a new number (which has not been present in the set before). In other words, the sequence of added numbers is a permutation of length $$$n$$$.

Every time Monocarp adds an element into the set except for the first time, he writes out a character:

- if the element Monocarp is trying to insert becomes the maximum element in the set, Monocarp writes out the character >;
- if the element Monocarp is trying to insert becomes the minimum element in the set, Monocarp writes out the character <;
- if none of the above, Monocarp writes out the character ?.

You are given a string $$$s$$$ of $$$n-1$$$ characters, which represents the characters written out by Monocarp (in the order he wrote them out). You have to process $$$m$$$ queries to the string. Each query has the following format:

- $$$i$$$ $$$c$$$ — replace $$$s_i$$$ with the character $$$c$$$.

Both before processing the queries and after each query, you have to calculate the number of different ways to order the integers $$$1, 2, 3, \dots, n$$$ such that, if Monocarp inserts the integers into the set in that order, he gets the string $$$s$$$. Since the answers might be large, print them modulo $$$998244353$$$.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 3 \cdot 10^5$$$; $$$1 \le m \le 3 \cdot 10^5$$$).

The second line contains the string $$$s$$$, consisting of exactly $$$n-1$$$ characters <, > and/or ?.

Then $$$m$$$ lines follow. Each of them represents a query. Each line contains an integer $$$i$$$ and a character $$$c$$$ ($$$1 \le i \le n-1$$$; $$$c$$$ is either <, >, or ?).

Output

Both before processing the queries and after each query, print one integer — the number of ways to order the integers $$$1, 2, 3, \dots, n$$$ such that, if Monocarp inserts the integers into the set in that order, he gets the string $$$s$$$. Since the answers might be large, print them modulo $$$998244353$$$.

Examples

Input

6 4 <?>?> 1 ? 4 < 5 < 1 >

Output

3 0 0 0 1

Input

2 2 > 1 ? 1 <

Output

1 0 1

Note

In the first example, there are three possible orderings before all queries:

- $$$3, 1, 2, 5, 4, 6$$$;
- $$$4, 1, 2, 5, 3, 6$$$;
- $$$4, 1, 3, 5, 2, 6$$$.

After the last query, there is only one possible ordering:

- $$$3, 5, 4, 6, 2, 1$$$.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/11/2023 08:28:29 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|