Consider two sets of integers represented in arrays, X = [x1, x2, . . . , xn] and Y =
[y1, y2, . . . , yn]. Write two versions of a FindSetUnion(X, Y ) algorithm to find the union of X
and Y as an array. An element is in the union of X and Y if it appears in at least one of X and Y .
You may make use any algorithm introduced in the lectures to help you develop your solution. That
is, you do not have to write the ‘standard’ algorithms – just use them. Therefore, you should be able
to write each algorithm in about 10 lines of code. You must include appropriate comments
in your pseudocode.

question:

(a) [2 Marks] Write a pre-sorting based algorithm of FindSetUnion(X, Y ). Your algorithm
should strictly run in O(n log n).
(b) [2 Marks] Write a Hashing based algorithm of FindSetUnion(X, Y ). Your algorithm should
run in O(n).

Python language!!!!!

№1

The translation from the Berland language into the Birland language is not an easy task. Those languages are very similar: a berlandish word differs from a birlandish word with the same meaning a little: it is spelled (and pronounced) reversely. For example, a Berlandish word code corresponds to a Birlandish word edoc. However, it's easy to make a mistake during the «translation». Vasya translated word s from Berlandish into Birlandish as t. Help him: find out if he translated the word correctly.

Input

The first line contains word s, the second line contains word t. The words consist of lowercase Latin letters. The input data do not consist unnecessary spaces. The words are not empty and their lengths do not exceed 100 symbols.

Output

If the word t is a word s, written reversely, print YES, otherwise print NO.

Examples

input

code
edoc

output

YES

№2

Anton likes to play chess, and so does his friend Danik.

Once they have played n games in a row. For each game it's known who was the winner — Anton or Danik. None of the games ended with a tie.

Now Anton wonders, who won more games, he or Danik? Help him determine this.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of games played.

The second line contains a string s, consisting of n uppercase English letters 'A' and 'D' — the outcome of each of the games. The i-th character of the string is equal to 'A' if the Anton won the i-th game and 'D' if Danik won the i-th game.

Output

If Anton won more games than Danik, print "Anton" (without quotes) in the only line of the output.

If Danik won more games than Anton, print "Danik" (without quotes) in the only line of the output.

If Anton and Danik won the same number of games, print "Friendship" (without quotes).

Examples

input

6
ADAAAA

output

Anton

№3

You can not just take the file and send it. When Polycarp trying to send a file in the social network "Codehorses", he encountered an unexpected problem. If the name of the file contains three or more "x" (lowercase Latin letters "x") in a row, the system considers that the file content does not correspond to the social network topic. In this case, the file is not sent and an error message is displayed.

Determine the minimum number of characters to remove from the file name so after that the name does not contain "xxx" as a substring. Print 0 if the file name does not initially contain a forbidden substring "xxx".

You can delete characters in arbitrary positions (not necessarily consecutive). If you delete a character, then the length of a string is reduced by 11. For example, if you delete the character in the position 22 from the string "exxxii", then the resulting string is "exxii".

Input

The first line contains integer nn (3≤n≤100)(3≤n≤100) — the length of the file name.

The second line contains a string of length nn consisting of lowercase Latin letters only — the file name.

Output

Print the minimum number of characters to remove from the file name so after that the name does not contain "xxx" as a substring. If initially the file name dost not contain a forbidden substring "xxx", print 0.

Examples

input

6
xxxiii

output

1

write a persuasive essay of 250 words about the use of technology .

Implement a dictionary application using C++ with the following features:

• Load a dictionary file.

• Given a prefix string that the user specifies, print the first word or all words in the dictionary with that string as their prefix.

• Given two strings A and B that the user specifies, replace all occurrences of A in the dictionary file with B.

• Spawning a new editor (e.g., vim) to allow the user to modify the dictionary file. Save the dictionary file afterwards.

You must use either C or C++ to implement your dictionary application. All your source code must be put within one (1) file. You will only submit that one file.

Your program should not have any extra library dependencies.

Please provide the coding in C++.

Person class
You will implement the Person Class in Visual Studio. A person object may be associated with multiple accounts. A person initiates activities (deposits or withdrawal) against an account that is captured in a transaction object.
A short description of each class member is given below:

Person
Class
Fields
-   password : string

Properties
+   «C# property, setter private» IsAuthenticated : bool
+   «C# property, setter absent» SIN : string
+   «C# property, setter absent» Name : string

Methods
+   «Constructor» Person(name : string, sin : string)
+   Login(password : string) : void
+   Logout() : void
+   ToString() : string

Fields:
⦁   password – this private string field represents the password of this person.
(N.B. Password are not normally stored as text but as a hash value. A hashing function operates on the password and the result is stored in the field. When a user supplies a password it is passed through the same hashing function and the result is compared to the value of the field.).
Properties:
⦁   SIN – this string property represents the sin number of this person. This getter is public and setter is absent.
⦁   IsAuthenticated – this property is a bool representing if this person is logged in with the correct password. This is modified in the Login() and the Logout() methods. This is an auto-implemented property, and the getter is public and setter is private
⦁   Name – this property is a string representing the name of this person. The getter is public and setter is absent.
Methods:
⦁   public Person( string name, string sin ) – This public constructor takes two parameters: a string representing the name of the person and another string representing the SIN of this person. It does the following:
⦁   The method assigns the arguments to the appropriate fields.
⦁   It also sets the password to the first three letters of the SIN. [use the Substring(start_position, length) method of the string class]
⦁   public void Login( string password ) – This method takes a string parameter representing the password and does the following:
⦁   If the argument DOES NOT match the password field, it does the following:
⦁   Sets the IsAuthenticated property to false
⦁   Creates an AccountException object using argument AccountEnum.PASSWORD_INCORRECT
⦁   Throws the above exception
⦁   If the argument matches the password, it does the following:
⦁   Sets the IsAuthenticated property is set to true
This method does not display anything
⦁   public void Logout( ) – This is public method does not take any parameters nor does it return a value.
This method sets the IsAuthenticated property to false
This method does not display anything
⦁   public override string ToString( )– This public method overrides the same method of the Object class. It returns a string representing the name of the person and if he is authenticated or not.
ITransaction interface
You will implement the ITransaction Interface in Visual Studio. The three sub classes implement this interface.
A short description of each class member is given below:

ITransaction
Interface
Methods
   Withdraw(amount : double, person : Person) : void
   Deposit(amount : double, person : Person) : void

Methods:
⦁   void Withdraw(double amount, Person person).
⦁   void Deposit(double amount, Person person).

Transaction class
You will implement the Transaction Class in Visual Studio. The only purpose of this class is to capture the data values for each transaction. A short description of the class members is given below:
All the properties are public with the setter absent.
Transaction
Class
Properties
+   «C# property, setter absent » AccountNumber : string
+   «C# property, setter absent» Amount : double
+   «C# property, setter absent» Originator : Person
+   «C# property, setter absent» Time : DateTime

Methods
+   «Constructor» Transaction(accountNumber : string, amount : double, endBalance : double, person : Person, time : DateTime)
+   ToString() : string

Properties:
All the properties are public with the setter absent
⦁   AccountNumber – this property is a string representing the account number associated with this transaction. The getter is public and the setter is absent.
⦁   Amount – this property is a double representing the account of this transaction. The getter is public and the setter is absent.
⦁   Originator – this property is a Person representing the person initiating this transaction. The getter is public and the setter is absent.
⦁   Time – this property is a DateTime (a .NET built-in type) representing the time associated with this transaction. The getter is public and the setter is absent.
Methods:
⦁   public Transaction( string accountNumber, double amount, Person person, DateTime time ) – This public constructor takes five arguments. It assigns the arguments to the appropriate fields.
⦁   public override string ToString( ) – This method overrides the same method of the Object class. It does not take any parameter and it returns a string representing the account number, name of the person, the amount and the time that this transition was completed. [you may use ToShortTimeString() method of the DateTime class]. You must include the word Deposit or Withdraw in the output.
A better type would have been a struct instead of a class.
ExceptionEnum enum
You will implement this enum in Visual Studio. There are seven members:
ACCOUNT_DOES_NOT_EXIST,
CREDIT_LIMIT_HAS_BEEN_EXCEEDED,
NAME_NOT_ASSOCIATED_WITH_ACCOUNT,
NO_OVERDRAFT,
PASSWORD_INCORRECT,
USER_DOES_NOT_EXIST,
USER_NOT_LOGGED_IN
The members are self-explanatory.
AccountException class
You will implement the AccountException Class in Visual Studio. This inherits from the Exception Class to provide a custom exception object for this application. It consists of seven strings and two constructors:
AccountException
Class
→ Exception
Fields

Properties

Methods
+   «Constructor» AccountException(reason : ExceptionEnum)

Fields:
There are no fields
Properties:
There are no properties
Methods:
⦁   AccountException( ExceptionEnum reason )– this public constructor simply invokes the base constructor with an appropriate argument. Use the ToString() of the enum type.

M = [4,3,7,6,5,2,4,1,0,7]

Construct a binary search tree for M. Then traverse it (post order)

Written in C++. I need to create function printShort exactly like this description: "printShort ( ) - prints the Date in the format m/d/yy (no leading zeros for month and day, and two last digits for year with leading zeros (use fill digit ‘0’) if necessary). Use the accessors to get the values of the data members. " Right now it is showing the correct output for month and day, but still printing a 4 digit year. How would I only print the last two digits of the variable year? For example, with March 31, 2020 the year's value is set to '2020', but it should be written 3/31/20

Function code:

void Date::printShort(){

    cout<<getMonth()<<"/";
    cout<<getDay()<<"/";
    cout<<setfill('0')<<setw(2)<<getYear();

}//end printShort

Q1. [10 pts, 1pt each] General knowledge of Computer, True or False (fill in T or F)

1. (      ) Register is implemented inside the main memory on computer board.
2. (      ) Von Neumann architecture has data and instructions in the same memory.
3. (      ) Servers are the largest class of computers and span the widest range of applications and performance.
4. (      ) Control unit is active part of the computer, following the instructions of the program to the letter. It adds numbers, tests numbers, controls other components, and so on.
5. (      ) Assembler translates from a high-level notation to assembly language.
6. (      ) Input device is a mechanism that conveys the result of a computation to a user or another computer.
7. (      ) ISA is the interface between software and hardware.
8. (      ) The MIPS architecture as simulated in QtSpim is big-endian.
9. (      ) The addressing mode of instruction sw $t0,32($s0) is PC-relative addressing mode.
10. (      ) Memory in MIPS architecture can store 2³² words.

Python Questions：

Q1. list_1= ['wind', 'spring', 'summer', 'purse', 'great', 'sports']

Use re.search() in the re package and list comprehension to find all words in list_1 that does not contain the letter "r".

Q2.

str_1= '''I live in a room by the sea,
where the view is great and the food is free.
Some of the tenants come and go.
Some I eat, if they're too slow.
One end of me is firmly locked.
The other end just gently rocks.
I live in a room by the sea.
It's perfect for an anemone. '''
Use re.search() in the re package to find all lines that does not start with the letter "s", "S", or "I".

Q3. list_1= ['attitudes', 'ab\nchild', '2!apologies', 'echess', 'fly\n', 'cheer']
Use list comprehension and functions in re package to filter all elements that start with "ch" or end with "es".

Q4. Remove everything from the first occurrence of "e" till end of the string, using the function .sub() from the "re" package

str_1 = 'Two things are infinite: the universe and human stupidity; and I'm not sure about the universe.'

The below mentioned figure shows a General diagnosis flowchart for troubleshooting HP servers. Use
the flowchart to create a C++ program that leads a person through the steps of fixing a bad HP server.
Here is an example of the program’s output (following one of the flow):
Starting General Diagnosis Program.
Recoding symptoms information - DONE.
Rebooting server to see if condition still exists - DONE.
Is this a newly installed server? yes [enter]
Please reseat any components that may have come loose during shipping - DONE.
Rebooting the server - DONE.
Does the condition still exist? no [enter]
Recording all actions taken for future - DONE.
Congratulations, your server problems are solved.
Notice the program ends as soon as a solution is found to the problem.

A situation in which the source of information is more sensitive than the information itself. Explain why the sum of sensitive data might also be sensitive.

*****Software Engineering

Define the following :

QUESTION 1

1.1) Contract Software

1.2) Internal Software Development

1.3) Client

1.4) Object

Briefly describe an example scenario where a strategy design pattern is suitable to use.

Answer the following multiple-choice questions:

1. A TCP receiver received an expected segment, without error, but yet has not ACKed the sender. What might be the reason for that?

1. It is actually a lost segment.
2. It is actually a duplicate segment.
3. The use of Stop-and-wait mechanism.
4. The use of Delayed ACK.
5. The use of a large window size.

2. If a TCP receiver received 2 segments with sequence number 34 and 58, the second segment was corrupted and discarded. What action could be taken to fix this? (Recall in TCP, ACK number is the next expected 1st byte number in the next segment & TCP uses cumulative ACK means all segments received with sequence number less than ACK number have been received correctly)

1. Receiver sends ACK number 34
2. Receiver sends ACK number 58
3. Receiver sends ACKs number 34 & 58
4. Receiver just waits for timeout

3. Receiver Window value in TCP header is used for ___________

1. Go-back N window
2. Flow control
3. Congestion avoidance
4. Establish connection

4. Comparing TCP to UDP: choose ALL CORRECT statements

1. UDP server can support multiple clients using one socket.
2. TCP server can support multiple clients using one socket.
3. TCP server can support multiple clients using multiple sockets.
4. TCP server cannot allow a client to have more than one connection socket.
5. TCP server allow a client to have more than one connection socket

5. What is NOT true about TCP congestion control?

1. TCP sender’s experience slow rate at the beginning of the connection
2. After a slow start, TCP sender’s initial rate increases slowly
3. After a slow start, TCP sender’s initial rate increases exponentially (fast)
4. when loss occurs, congestion window is cut down to half

6. A reliable data transfer mechanism in which receiver individually acknowledges all correctly received packets and sender only resends packets for which ACK not received is called:

1. Go-back-N
2. Selective repeat
3. Negative acknowledgement
4. NAK-free protocol

7. Consider a TCP connection between Host A and B. Suppose that the TCP segments traveling from Host A to Host B have source port number x and destination port number y. What are the source and destination port numbers for the segments traveling from Host B to Host A?

1. source port number x and destination port number x
2. source port number x and destination port number y
3. source port number y and destination port number x
4. source port number y and destination port number y
5. No enough information

8. Consider an RDT protocol. To find whether a received packet (at the receiver) contains new data or it is a duplicate, we can use ________________.

1. Sequence numbers
2. Acknowledgement
3. Duplicate Acknowledgement
4. Timers
5. Pipelining
6. Checksum

Pycharm

Complete the Place class that has the following attributes for place(name, country, priority and visited status) and the methods:

__init__

__str__

two methods to mark the place as unvisited\visited

Then in complete a list of Place objects in Places_Features class and the following methods.

load_places (from txt file into Place objects in the list)

save_places (from place list into output list)

add_place (add a place in the place list)

input.txt

Lima,Peru,3,n
Auckland,New Zealand,1,v
Rome,Italy,12,n

Can make the main.py give the following output

Output

* Lima in Peru priority 3
* Rome in Italy priority 12
Auckland in New Zealand priority 1
3 places. You still want to visit 2 places