2024 Xiangtan University Summer Camp-Div.1
A. Coin
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

$$$n$$$ individuals are betting on coins, and Eric is ranked $$$x$$$ at the beginning. Each round will divide these $$$n$$$ individuals into $$$\frac{n}{2}$$$ groups, with each group playing one game. In each match, the probability of two people winning is equal. After each match, if the person at the bottom of the rankings wins, then the rankings of the two people are swapped, otherwise the rankings of the two people remain unchanged.

Find the expected ranking of Eric after $$$k$$$ rounds, modeling $$$998244353$$$.

Input

One line contains two integers $$$n,x,k(1\le n,k\le 10^{18},1\le x \le n)$$$, $$$n$$$ is even.

Output

One line contains one integer — the expected ranking of EricXie after $$$k$$$ rounds, modeling $$$998244353$$$.

Examples
Input
2 2 2
Output
499122178
Input
114 5 14
Output
34643733

B. Game
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Eric is playing a game with Cire.

The game is played over a sequence of length n. Eric takes the first turn, and the two players alternate actions. On each turn, a player can do one of the following two actions:

  • Delete the smallest number in the sequence (or any number if there are more than one).
  • Reduce all the numbers in the sequence by 1. This action assumes that all the numbers in the sequence are greater than 0.

If the sequence is empty after a person's operation, he wins the game.

Now you are given a sequence and you need to determine who will win the game.

Input

The first line contains an integer $$$n(1\le n \le 10^6)$$$.

The second line contains $$$n$$$ integers $$$a_1,a_2,\cdots,a_n(0\le a_i \le 10^{18})$$$, which denote the sequence.

Output

If Eric will win the game, output "Eric". otherwise, output "Cire".

Examples
Input
1
14514
Output
Eric
Input
7
1 9 1 9 8 1 0
Output
Cire

C. Genshin Impact
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You're right, but Genshin Impact is an open-world adventure game produced and published by Shanghai Mihoyo Network Technology Co. The game takes place in a fantasy world called "Tivat Continent", where players can take on the role of a mysterious character called "Traveler", interact with various characters, and complete various quests. The game features an anime-inspired open-world environment with a basic free-to-play and pay-per-use system based on card draw. Players can explore, fight, and collect various resources to level up their characters and combat power. The game also offers a variety of battle mechanics and character development systems, allowing players to experience different battle experiences.

However, there's a lot of vitriol against Genshin Impact on the internet, and for that reason, Eric needs to set up some blocked words to maintain harmony in the online community.

Eric specifies a string as the blocked word of lowercase letters. Nonetheless, he is still unsure, so he uses the result of any rearrangement of that string, as well as their subsequences, as a blocked word.

For instance, if Eric chooses "genshin" as the blocked word, "nn", "hnn", "nihneg" will be blocked, "nnn", "gg" will be allowed to use.

Now give you the string $$$S$$$ Eric choose. You need to count how many blocked words there are of each length from 1 to $$$|S|$$$, computed modulo $$$998244353$$$.

Input

One line, the string $$$S(1\le |S|\le 10^5)$$$.

Output

One line contains $$$n$$$ number, the number of blocked words of each length, computed modulo $$$998244353$$$.

Examples
Input
genshin
Output
6 31 135 480 1320 2520 2520 
Input
abcde
Output
5 20 60 120 120 

D. Iwanna
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Eric has developed an iwanna game. Now he invites you to participate in a test of his game.

The game map can be viewed as an $$$n$$$-node tree, connected by $$$n-1$$$ weighted edges.

In a game, the player has to walk from the starting point $$$s$$$ to the finishing point $$$t$$$. As soon as the player moves to point $$$t$$$, the game ends. Since the player does not know where the end point is, the player will follow the following strategy: Assuming that the player is currently at point $$$x$$$, if there exists an unvisited neighboring node of point $$$x$$$, the player will randomly choose one of all the unvisited neighboring nodes to go to; otherwise, the player will go to the earliest visited node among its neighboring nodes.

The cost of a single game is the sum of the weights of the visited edges on the path (multiple passes of the same edge require multiple computations).

In order to test the game, Eric asks you q questions, giving you the starting point $$$s$$$ and the end point $$$t$$$ for each question. You need to answer the expected cost for each question, computed modulo $$$998244353$$$.

Input

The first line contains two integers $$$n,q(1\le n,q \le 5\cdot 10^5)$$$.

For the next $$$n-1$$$ lines, each line contains three integers $$$u,v,w(1\le u,v \le n,1\le w \le 10^9)$$$, denoting an edge connecting u,v with weight w.

For the next $$$q$$$ lines, each line contains two integers $$$s,t(1\le s,t \le n)$$$.

Output

$$$q$$$ lines, each line contains an integer—the expected cost for each question, computed modulo $$$998244353$$$.

Examples
Input
3 3
1 2 1
2 3 2
1 2
2 3
1 3
Output
1
3
3
Input
5 5
1 2 1
1 3 2
1 4 4
1 5 8
2 1
5 1
4 5
3 4
4 4
Output
1
8
15
15
0

E. League of Legends
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

League of Legends (LoL), commonly referred to as League, is a 2009 multiplayer online battle arena video game developed and published by Riot Games. Inspired by Defense of the Ancients, a custom map for Warcraft III, Riot's founders sought to develop a stand-alone game in the same genre. Since its release in October 2009, League has been free-to-play and is monetized through purchasable character customization. The game is available for Microsoft Windows and macOS.

Eric and Clamee are playing Mundo Solo in Summon Canyon. Eric's Mundo has $$$n$$$ HP, while Clamee's Mundo has $$$m$$$ HP. The game ends when one's Mondo is reduced to $$$0$$$ HP. Eric is a Mondo grandmaster, so he will unleash Mondo's Q skill each turn. Clamee doesn't know how to play this game; hence, he will do nothing each turn. Mondo's skill is to cut himself by one HP, throw a dagger, and if it hits, cut the opponent by one HP. Eric's hit rate per Q skill is $$$\frac{1}{2}$$$.

Please find the probability that Eric's Mondo and Clamee's Mondo's HP will both go to 0 after a Q skill, computed modulo $$$998244353$$$.

Input

Each test consists of multiple test cases. The initial line presents a single integer $$$T~(1\le T\le 10^5)$$$ , which denotes the quantity of test cases.

In the context of each test instance, it contains one line presents two integers $$$n,m~(1\le n,m\le 10^6)$$$.

Output

For each test case, you are to output a single line containing the probability that Eric's Mondo and Clamee's Mondo's HP will both go to 0 after a Q skill, computed modulo $$$998244353$$$.

Example
Input
4
1 1
1 2
2 1
2 2
Output
499122177
0
748683265
748683265

F. Tetris
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Tetris (Russian: Тетрис) is a puzzle video game created in 1985 by Alexey Pajitnov, a Soviet software engineer. It has been published by several companies on more than 65 platforms, setting a Guinness world record for the most ported game. After a significant period of publication by Nintendo, in 1996 the rights reverted to Pajitnov, who co-founded the Tetris Company with Henk Rogers to manage licensing.

The pieces on which the game of Tetris is based are called "tetrominoes". Pajitnov's original version for the Electronika 60 computer used green brackets to represent the blocks that make up tetrominoes. Versions of Tetris on the original Game Boy/Game Boy Color and on most dedicated handheld games use black-and-white or grayscale graphics, but most popular versions use a separate color for each distinct shape. Prior to the Tetris Company's standardization in the early 2000s, those colors varied widely from implementation to implementation.

All seven tetrominoes using the standard color scheme

Here Eric invented a new way to play Tetris. Players are given a $$$n\cdot m$$$ map with obstacles. Players need to fill the map with six tetrominoes below:

Six tetrominoes used in Eric's game

Note that there is a tetromino that can't be used in Eric's game.

The player can rotate a tetromino 0, 90, 180, or 270 degrees before he fills it.

In Eric's game, you can't make tetrominoes cover obstacles or go beyond the map boundaries. Given a map, you need to find the maximum number of tetrominoes you can fill.

Input

The first line contains two integers $$$n, m(1\le n,m \le 100)$$$.

For the next $$$n$$$ lines, each line contains $$$m$$$ characters. Each character is either a "0" or a "1", where "0" is an open space and "1" is an obstacle.

Output

An integer, representing the maximum number of tetrominoes you can fill.

Examples
Input
3 3
000
010
000
Output
2
Input
2 2
11
01
Output
0
Input
5 5
00100
01100
01001
10000
01100
Output
4