[구인] C++ Senior Programmer

SK C&C E-PRJ팀에서는 C++ Senior Programmer를 모집합니다.

* 담당 업무
항공 사진을 이용한 3D Mirror World Production System 개발
cluster 로 이루어진 production system 에서 동작할 대용량 이미지 처리 s/w 구현

* 지원 자격 및 우대 사항
성별/연령/학력 불문

C++ 전문 개발 경력 5년 이상
C/C++ Expert
팀 작업에 익숙하고 다른 사람들과의 커뮤니케이션에 문제가 없는 자
영문 기술 문서 읽기에 익숙하신 분
다양한 상용/공개 라이브러리를 사용해본 경험자 우대
GIS/Computer Graphics/Computer Vision/Numerical Analysis 경험자 우대

* 대우
정직원

* 연봉
추후 협의

* 복리후생
연금/보험 : 국민연금, 고용보험, 산재보험, 건강보험
휴무/휴가 : 주5일 근무, 연차, 정기 휴가
보상 제도 : 인센티브제
건강관리 지원 : 건강검진, 본인 의료비 지원
생활안정 지원 : 자녀 학자금 지원, 직원대출제도
생활편의 지원 : 사원식당, 통근버스 운행
경조사 지원 : 각종 경조금, 경조휴가제
교육/여가 지원 : 자기계발비 지원
기타 : 사내 헬스 센터/의무실/어린이집 운영

* 전형 절차
기술 필기 -> 실무자 면접 -> 임원진 면접 -> 합격자 발표

* 기술 필기
다음의 문제 중 4문제 이상을 풀어 source code를 메일로 제출
C++ 을 사용할 것. STL/MFC 사용하지 말 것.

• The 3n + 1 problem
• Prime Ring Problem
  
• The Settlers of Catan
  
• Anagram
  
• Wormholes
• Re-connecting Computer Sites
• Password Search
• 2D Representations
• Telephone Directory Alphabetization
• Dividing up
• Overlapping Air Traffic Control Zones
• Caesar Cypher

* 제출 서류 (담당자에게 이메일 제출)
기술 필기 시험 결과 (program source code)
이력서
Project 경력 기술서

* 담당자













* 기타
E-PRJ팀은 개발자를 구인 중입니다. programming을 직접 하실 분만 지원 부탁드립니다. (PM 직군은 신규 채용 예정이 없습니다.)
문의 사항이 있으신 분은 담당자에게 연락 부탁드립니다.

회사 이메일 주소가 안되시는 분은 개인 이메일 주소 naraofbaram at gmail.com 으로 보내주시기 바랍니다.

[Job Offer] Program Manager

The SK C&C 3D Mirror World team is looking for program managers (PM) for creating a 3D virtual globe of the Earth. The successful PM has a graduate degree, preferable a PhD in a field closely related to the subject such as computer vision, photogrammetry, or GIS combined with 5+ years of relevant industry experience.

Expected are in-depth knowledge of digital image processing, digital photogrammetry, 2D and 3D geometry, multiple view geometry and a proven track record in developing software algorithm. Experience with true ortho-imagery, close range photogrammetry and oblique aerial imagery are especially relevant for this position.

To apply, please send resume and salary history/requirements in word/pdf documents to naraofbaram@skcc.com .

[Job Offer] C++ Senior Programmer

SK C&C, a Korean IT outsourcing and SI consulting company is seeking for Programmer / Senior Programmer for newly developing Earth Browser Project. The ideal applicant will be proficient in programming C++, specialized for Computer Vision / Photogrammetry. We are looking for a highly skilled, experienced, self-motivated and creative programmer who has solid coding, troubleshooting and analytical skills, an in-depth knowledge of C++ and who thrives on delivering unique solutions to customers within an advanced product incubation environment.

Requirements :

* Expert C++ programming skills

* 5+ years of professional software development

* MS or PhD in Computer Science, Applied Math or a related technical field

* Excellent verbal and written communication skills in English

* Self-motivation

Plusses :

* Expertise in developing state of the art 3D reconstruction algorithms from still photo or video data using a combination of computer vision and photogrammetric methodologies

* Familiarity with image processing, mapping, and geospatial technologies

* Graduate level study of computer vision, numerical analysis, and probability related disciplines

To apply, please send resume, salary history/requirements in word/pdf documents, and answers from following questions - from at least 3 questions - in plain text to naraofbaram@skcc.com .

• The 3n + 1 problem
• Prime Ring Problem
  
• The Settlers of Catan
  
• Anagram
  
• Wormholes
• Re-connecting Computer Sites
• Password Search
• 2D Representations
• Telephone Directory Alphabetization
• Dividing up
• Overlapping Air Traffic Control Zones
• Caesar Cypher

Re-connecting Computer Sites

Consider the problem of selecting a set T of high-speed lines for connecting N computer sites, from a universe of M high-speed lines each connecting a pair of computer sites. Each high-speed line has a given monthly cost, and the objective is to minimize the total cost of connecting the N computer sites, where the total cost is the sum of the cost of each line included in set T. Consider further that this problem has been solved earlier for the set of N computer sites and M high-speed lines, but that a few K new high-speed lines have recently become available.

Your objective is to compute the new set T' that may yield a cost lower than the original set T, due to the additional K new high-speed lines and when M+K high-speed lines are available.

Input

The input will contain several test cases, each of them as described below. Consecutive test cases are separated by a single blank line.

The input is organized as follows:

• A line containing the number N of computer sites, with 1 <= N <= 1000000, and where each computer site is referred by a number i, 1 <= i <= N.
• The set T of previously chosen high-speed lines, consisting of N-1 lines, each describing a high-speed line, and containing the numbers of the two computer sites the line connects and the monthly cost of using this line. All costs are integers.
• A line containing the number K of new additional lines, 1 <= K <= 10.
• K lines, each describing a new high-speed line, and containing the numbers of the two computer sites the line connects and the monthly cost of using this line. All costs are integers.
• A line containing the number M of originally available high-speed lines, with N-1 <= M <= N (N-1) / 2.
• M lines, each describing one of the originally available high-speed lines, and containing the numbers of the two computer sites the line connects and the monthly cost of using this line. All costs are integers.

Output

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

The output file must have one line containing the original cost of connecting the Ncomputer sites with M high-speed lines and another line containing the new cost of connecting the N computer sites with M+K high-speed lines. If the new cost equals the original cost, the same value is written twice.

Sample Input

5 

1 2 5 

1 3 5 

1 4 5 

1 5 5 

1

2 3 2 

6 

1 2 5 

1 3 5 

1 4 5 

1 5 5 

3 4 8 

4 5 8 

Sample Output

20 

17 

Password Search

Being able to send encoded messages during World War II was very important to the Allies. The messages were always sent after being encoded with a known password. Having a fixed password was of course insecure, thus there was a need to change it frequently. However, a mechanism was necessary to send the new password. One of the mathematicians working in the cryptographic team had a clever idea that was to send the password hidden within the message itself. The interesting point was that the receiver of the message only had to know the size of the password and then search for the password within the received text.

A password with size N can be found by searching the text for the most frequent substring with N characters. After finding the password, all the substrings that coincide with the password are removed from the encoded text. Now, the password can be used to decode the message.

Problem

Your mission has been simplified as you are only requested to write a program that, given the size of the password and the encoded message, determines the password following the strategy given above.

To illustrate your task, consider the following example in which the password size is three (N=3) and the text message is just baababacb. The password would then be aba because this is the substring with size 3 that appears most often in the whole text (it appears twice) while the other six different substrings appear only once (baa ; aab ; bab ; bac ; acb).

Input

The input file contains several test cases, each of them consists of one line with the size of the password, 0 < N ≤10, followed by the text representing the encoded message. To simplify things, you can assume that the text only includes lower case letters.

Output

For each test case, your program should print as output a line with the password string.

Sample Input

3 baababacb 

Sample Output

aba   

2D Representations

2D Representations

Background

   A 2D raster image is defined by a matrix of points or pixels. In a black and white raster image, each pixel (a matrix element) can be black (full) or white (empty). There are several methods known to represent a raster image. Two of them, are the "Quadtree" and the "Run Length code".
   In a Quadtree, the matrix is preferably square with a length that is a power of two. One image is represented following a recursive visit: the image is divided in four image cells (accordingly to the order shown in Figure 1) and each cell is evaluated to be Full, Empty, or Partial. When a Partial cell is found, it is recursively subdivided in four cells and the same principle is repeated again and again until the cell is completely Full or completely Empty. The structure of a quadtree is a tree of nodes and each node can have from zero to four descendents (see Figure 1).

Figure 1 - One image, the order of visit and the quadtree

   In the Run Length code, pixels are grouped in series of empty pixels, full pixels and empty pixels again, etc. In this way, the image can be represented as a series of numbers, being each number of pixels in a group (we can assume that the first group is composed of full pixels). Using the image of Figure 1 as an example, the run length code is: 0, 20, 4, 4, 9, 1, 1, 1, 4, 1, 1, 2, 4, 4, 4, 4 (considering the lower left pixel as the first one).

Problem

   Given an image in the form of a quadtree, the problem is to obtain the correspondent run length code. The image maximum size is 256*256 and the origin of coordinates is the lower left pixel.

Input

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

   The first line of the input contains the length of the image and the second line contains the number of nodes Nto be considered (both in integer format). Each one of the following N lines describes a different node (in sequence, starting with node 1), with four fields separated by a space. Each field may be one character F (full) or E (empty) or a number that is the index of a descendent node.

Output

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

   One line with the run length code of the given image (integers separated by a space). Note that the first group is assumed to be Full.

Sample Input
1

8
5
E 2 F 3
E E F F
4 5 E E
F E E F
F E E E

Sample Output
0 20 4 4 9 1 1 1 4 1 1 2 4 4 4 4

 

Telephone Directory Alphabetization

Based on its success in contracting previous software development efforts to programming contest teams, the String & Tin Can (S&TC) Telephone Company has now decided to produce its telephone directories internally. Your team has been hired to develop a program that will take subscriber names and telephone numbers and alphabetize them into a list for printing.

Telephone directories have traditionally used special conventions for alphabetization, and S&TC wants your program to use these conventions. Each subscriber listing consists of one or more ``words,'' where each word is separated from the others by spaces or non-alphanumeric characters. Directories only use the letters A through Z for sorting, ignoring case. Therefore, names that include words comprised of digits or capital letters require special processing.

A listing may contain a word that is a decimal number. Listings with numbers in them appear in the alphabetized list in the same location they would if the numbers were spelled out in English. For example, ``50 Star Company'' might appear just before ``Fifty Star Vending'' in the list. Numbers are permitted to be in the range 0-999,999,999. Letters and digits will not appear together in the same word.

All special (non-alphanumeric) characters are to be treated as spaces. ``Penny-Wise Corporation'' would appear after ``Penny Saver,'' but before ``Pennypinching Company.'' Multiple spaces or non-alphanumeric characters are treated as a single space when sorting. Special characters will not appear at the beginning of a listing.

Words that are comprised of all capital letters are assumed to be initials or acronyms, and are treated as if spaces appeared between each letter. Hence, ``KAT Shop'' would appear at the beginning of the K listings, before ``K-B Enterprises'' and ``K Warehouse''.

Input 

Input to your program will be a list of subscribers, one per line. The first seven digits will be the telephone number, and the rest of the line will be the name of the subscriber as it is to appear in the telephone directory.

Output 

Your program is to alphabetically sort the subscriber names according to the rules above and print the listing in order. Each line should contain the subscriber name as it appeared in the input in the first 52 positions, left justified and space filled, followed by the seven digit telephone number (including a space between the third and fourth digits) in columns 56 through 63. The telephone number is to be immediately followed by the end of line.

Your program need not handle more than 1,000 subscribers-none of the towns S&TC serves in Swamp County have populations larger than that.

Sample Input 

8936251KAT Shop 

7362812Penny Saver, Inc. 

7251887Kate's Company 

8372974Fine Foods 

9273664Five Star Vending 

3523984K-B Enterprises 

723621899 Cents Only Store 

Sample Output 

Fine Foods                                             837 2974 

Five Star Vending                                      927 3664 

KAT Shop                                               893 6251 

K-B Enterprises                                        352 3984 

Kate's Company                                         725 1887 

99 Cents Only Store                                    723 6218 

Penny Saver, Inc.                                      736 2812 

Dividing up

Marsha and Bill own a collection of marbles. They want to split the collection among themselves so that both receive an equal share of the marbles. This would be easy if all the marbles had the same value, because then they could just split the collection in half. But unfortunately, some of the marbles are larger, or more beautiful than others. So, Marsha and Bill start by assigning a value, a natural number between one and six, to each marble. Now they want to divide the marbles so that each of them gets the same total value.

Unfortunately, they realize that it might be impossible to divide the marbles in this way (even if the total value of all marbles is even). For example, if there are one marble of value 1, one of value 3 and two of value 4, then they cannot be split into sets of equal value. So, they ask you to write a program that checks whether there is a fair partition of the marbles.

Input 

Each line in the input file describes one collection of marbles to be divided. The lines consist of six non-negative integers , where n_i is the number of marbles of value i. So, the example from above would be described by the input-line ``1 0 1 2 0 0''. The maximum total number of marbles will be 20000.

The last line of the input file will be ``0 0 0 0 0 0''; do not process this line.

Output 

For each colletcion, output ``Collection #k:'', where k is the number of the test case, and then either ``Can be divided.'' or ``Can't be divided.''.

Output a blank line after each test case.

Sample Input 

1 0 1 2 0 0 

1 0 0 0 1 1 

0 0 0 0 0 0 

Sample Output 

Collection #1: 

Can't be divided.  

Collection #2: 

Can be divided. 

Overlapping Air Traffic Control Zones

Optimization of air traffic flow is one of the essential ways for airlines to maintain economic viability. All too often, however, weather and other anomalous conditions disrupt air traffic flow resulting in significant costs. Automation systems for optimizing flows are not currently able to quickly reconfigure when path planning must account for dynamic conditions such as moving weather systems. Human intervention is usually used to decide route modifications.

Decisions on route modification for one aircraft must take into account neighboring aircraft safe zones in order to minimize possible collision risks. We will consider a 3D model in which the safe zone for one aircraft is represented as a parallelepiped.

Evaluation of aircraft collision risks, in this model, can be done by calculating the volume of the intersecting safe zones of the aircrafts in a given air traffic control zone. In other words, we need to be able to determine the volume of intersecting parallelepipeds.

Problem

Consider a number of parallelepipeds in space, having all the edges parallel to the axes. Your task is to write a program that outputs the volume occupied simultaneously by two or more parallelepipeds. Each parallelepiped is characterized by 6 integer values, the coordinates of two of its vertices

(x₁,y₁,z₁), (x₂, y₂,z₂) with x₁ < x₂, y₁ < y₂ and z₁ < z₂

Input

The input file contains several test cases, each of them consists of an integer 0 ≤ n ≥ 15 in the first line followed by n lines of 6-tuples of integers describing the parallelepipeds. The total area occupied does not exceed 5x10⁸.

Output

For each test case, output on a line by itself an integer corresponding to the total volume occupied simultaneously by two or more parallelepipeds.

Sample Input

  5
 1 1 3 3 3
   1 1 1 3 3 3
   1 1 1 3 3 3
   400000000 400000000 400000000 400000001 400000001 400000002
   400000000 400000000 400000000 400000002 400000004 400000001 

Sample Output

  9

Caesar Cypher

One of the earliest encrypting systems is attributed to Julius Caesar: if the letter to be encrypted is the Nth letter in the alphabet, replace it with the (N+K)th where K is some fixed integer (Caesar used K = 3). We usually treat a space as zero and all arithemtic is then done modulo 27. Thus for K = 1 the message `ATTACK AT DAWN' becomes `BUUBDLABUAEBXO'.

Decrypting such a message is trivial since one only needs to try 26 different values of K. This process is aided by knowledge of the language, since then one can determine when the decrypted text forms recognisable words. If one does not know the language, then a dictionary would be necessary.

Write a program that will read in a dictionary and some encrypted text, determine the value of K that was used, and then decrypt the cyphertext to produce the original message. The original message contained only letters and spaces and has been encrypted using the above method. The most suitable value of K will be the one which produces the most matches with the words in the dictionary.

Input 

Input will consist of a dictionary and the encrypted text. The dictionary will consist of no more than 100 lines each containing a word in uppercase characters and not more than 20 characters in length. The dictionary portion will be terminated by a line consisting of a single `#'. The encrypted text will follow immediately and will consist of a single line containing no more than 250 characters. Note that the dictionary will not necessarily contain all the words in the original text, although it will certainly contain a large portion of them. It may also contain words that are not in the original text. The dictionary will not appear in any particular order.

Output 

Output will consist of the decrypted text. Lines should be as long as possible, but not exceeding 60 characters and no word may cross a linebreak.

Sample Input 

THIS DAWN THAT THE ZORRO OTHER AT THING # BUUBDLA PSSPABUAEBXO 

Sample Output 

ATTACK ZORRO AT DAWN 

C++ Programmer 구인 공지

SK C&C E-PRJ팀에서는 C++ Programmer를 모집합니다.

* 담당 업무
항공 사진을 이용한 3D Mirror World Production System 개발
cluster 로 이루어진 production system 에서 동작할 대용량 이미지 처리 s/w 구현

* 지원 자격 및 우대 사항
성별/연령/학력/경력 불문
C/C++ Expert
팀 작업에 익숙하고 다른 사람들과의 커뮤니케이션에 문제가 없는 자
영문 기술 문서 읽기에 익숙하신 분
다양한 상용/공개 라이브러리를 사용해본 경험자 우대
GIS/Computer Graphics/Computer Vision/Numerical Analysis 경험자 우대

* 대우
정직원

* 연봉
추후 협의

* 복리후생
연금/보험 : 국민연금, 고용보험, 산재보험, 건강보험
휴무/휴가 : 주5일 근무, 연차, 정기 휴가
보상 제도 : 인센티브제
건강관리 지원 : 건강검진, 본인 의료비 지원
생활안정 지원 : 자녀 학자금 지원, 직원대출제도
생활편의 지원 : 사원식당, 통근버스 운행
경조사 지원 : 각종 경조금, 경조휴가제
교육/여가 지원 : 자기계발비 지원
기타 : 사내 헬스 센터/의무실/어린이집 운영

* 전형 절차
기술 필기 -> 실무자 면접 -> 임원진 면접 -> 합격자 발표

* 기술 필기
다음의 8문제 중 3문제 이상을 풀어 source code를 메일로 제출
C++ 을 사용할 것. STL/MFC 사용하지 말 것.

• The 3n + 1 problem
• Brick Wall Patterns
• Prime Ring Problem
• System Dependencies
• The Settlers of Catan
• The partition of a cake
• Anagram
• The Skyline Problem
• Wormholes

* 제출 서류 (담당자에게 이메일 제출)
기술 필기 시험 결과 (program source code)
이력서
Project 경력 기술서

* 담당자













* 기타
E-PRJ팀은 개발자를 구인 중입니다. programming을 직접 하실 분만 지원 부탁드립니다. (PM 직군은 신규 채용 예정이 없습니다.)
문의 사항이 있으신 분은 담당자에게 연락 부탁드립니다.

LC-Display

A friend of you has just bought a new computer. Until now, the most powerful computer he ever used has been a pocket calculator. Now, looking at his new computer, he is a bit disappointed, because he liked the LC-display of his calculator so much. So you decide to write a program that displays numbers in an LC-display-like style on his computer.

Input

The input file contains several lines, one for each number to be displayed. Each line contains two integers s, n ( ), where n is the number to be displayed and s is the size in which it shall be displayed.

The input file will be terminated by a line containing two zeros. This line should not be processed.

Output

Output the numbers given in the input file in an LC-display-style using s ``-'' signs for the horizontal segments and s ``|'' signs for the vertical ones. Each digit occupies exactly s+2 columns and 2s+3 rows. (Be sure to fill all the white space occupied by the digits with blanks, also for the last digit.) There has to be exactly one column of blanks between two digits.

Output a blank line after each number. (You will find a sample of each digit in the sample output.)

Sample Input

2 12345
3 67890
0 0

Sample Output

Brick Wall Patterns

If we want to build a brick wall out of the usual size of brick which has a length twice as long as its height, and if our wall is to be two units tall, we can make our wall in a number of patterns, depending on how long we want it. From the figure one observe that:

• There is just one wall pattern which is 1 unit wide - made by putting the brick on its end.
• There are 2 patterns for a wall of length 2: two side-ways bricks laid on top of each other and two bricks long-ways up put next to each other.
• There are three patterns for walls of length 3.

How many patterns can you find for a wall of length 4? And, for a wall of length 5?

Problem

Your task is to write a program that given the length of a wall, determines how many patterns there may be for a wall of that length.

Intput

Your program receives a sequence of positive integers, one per line, each representing the length of a wall. The maximum value for the wall is length 50. The input terminates with a 0.

Output

For each wall length given in the input, your program must output the corresponding number of different patterns for such a wall in a separate line.

Sample Intput

1
2
3
0

Sample Output

1
2
3

Wormholes

In the year 2163, wormholes were discovered. A wormhole is a subspace tunnel through space and time connecting two star systems. Wormholes have a few peculiar properties:

• Wormholes are one-way only.

• The time it takes to travel through a wormhole is negligible.

• A wormhole has two end points, each situated in a star system.

• A star system may have more than one wormhole end point within its boundaries.

• For some unknown reason, starting from our solar system, it is always possible to end up in any star system by following a sequence of wormholes (maybe Earth is the centre of the universe).

• Between any pair of star systems, there is at most one wormhole in either direction.

• There are no wormholes with both end points in the same star system.

All wormholes have a constant time difference between their end points. For example, a specific wormhole may cause the person travelling through it to end up 15 years in the future. Another wormhole may cause the person to end up 42 years in the past.

A brilliant physicist, living on earth, wants to use wormholes to study the Big Bang. Since warp drive has not been invented yet, it is not possible for her to travel from one star system to another one directly. This can be done using wormholes, of course.

The scientist wants to reach a cycle of wormholes somewhere in the universe that causes her to end up in the past. By travelling along this cycle a lot of times, the scientist is able to go back as far in time as necessary to reach the beginning of the universe and see the Big Bang with her own eyes. Write a program to find out whether such a cycle exists.

Input

The input file starts with a line containing the number of cases c to be analysed. Each case starts with a line with two numbers n and m . These indicate the number of star systems ( ) and the number of wormholes ( ) . The star systems are numbered from 0 (our solar system) through n-1 . For each wormhole a line containing three integer numbers x, y and t is given. These numbers indicate that this wormhole allows someone to travel from the star system numbered x to the star system numbered y, thereby ending up t ( ) years in the future.

Output

The output consists of c lines, one line for each case, containing the word possible if it is indeed possible to go back in time indefinitely, or not possible if this is not possible with the given set of star systems and wormholes.

Sample Input

2
3 3
0 1 1000
1 2 15
2 1 -42
4 4
0 1 10
1 2 20
2 3 30
3 0 -60

Sample Output

possible
not possible

The Settlers of Catan

Within Settlers of Catan, the 1995 German game of the year, players attempt to dominate an island by building roads, settlements and cities across its uncharted wilderness.

You are employed by a software company that just has decided to develop a computer version of this game, and you are chosen to implement one of the game's special rules:

When the game ends, the player who built the longest road gains two extra victory points.

The problem here is that the players usually build complex road networks and not just one linear path. Therefore, determining the longest road is not trivial (although human players usually see it immediately).

Compared to the original game, we will solve a simplified problem here: You are given a set of nodes (cities) and a set of edges (road segments) of length 1 connecting the nodes. The longest road is defined as the longest path within the network that doesn't use an edge twice. Nodes may be visited more than once, though.

Example: The following network contains a road of length 12.

Input

The input file will contain one or more test cases.

The first line of each test case contains two integers: the number of nodes n ( ) and the number of edges m ( ). The next m lines describe the m edges. Each edge is given by the numbers of the two nodes connected by it. Nodes are numbered from 0 to n-1. Edges are undirected. Nodes have degrees of three or less. The network is not neccessarily connected.

Input will be terminated by two values of 0 for n and m.

Output

For each test case, print the length of the longest road on a single line.

Sample Input

3 2
0 1
1 2
15 16
0 2
1 2
2 3
3 4
3 5
4 6
5 7
6 8
7 8
7 9
8 10
9 11
10 12
11 12
10 13
12 14
0 0

Sample Output

2
12

The partition of a cake

There is a 10001000 square cake. We use knife to cut the cake. The problem is after a series of cutting, how many partitions the cake will has.

Assumption:

1.

The number of the cutting will be no more than 8.

2.

After the cutting, the length of any edge of the partition will no less than 1.

3.

The vertex coordinates of the cake are (0,0)(0,1000)(1000,1000) (1000,0).

4.

The intersections of the cut line and the cake edge are two .

The following Graph is a sample partition. The number of the partitions is 10.

Input

The first line of the input is an integer M, then a blank line followed by M datasets. There is a blank line between datasets.The first line of each dataset is the number of the cutting . The following lines contain the information of the cut lines. Each line has 4 integer number, which represent the coordinate of the intersection of the cut line and the cake edge.

Output

The output for each dataset is the number of the partitions of the cake. Print a blank line between datasets.

Sample Input

1

3
0 0 1000 1000
500 0 500 1000
0 500 1000 500

Sample Output

6

System Dependencies

Components of computer systems often have dependencies--other components that must be installed before they will function properly. These dependencies are frequently shared by multiple components. For example, both the TELNET client program and the FTP client program require that the TCP/IP networking software be installed before they can operate. If you install TCP/IP and the TELNET client program, and later decide to add the FTP client program, you do not need to reinstall TCP/IP.

For some components it would not be a problem if the components on which they depended were reinstalled; it would just waste some resources. But for others, like TCP/IP, some component configuration may be destroyed if the component was reinstalled.

It is useful to be able to remove components that are no longer needed. When this is done, components that only support the removed component may also be removed, freeing up disk space, memory, and other resources. But a supporting component, not explicitly installed, may be removed only if all components which depend on it are also removed. For example, removing the FTP client program and TCP/IP would mean the TELNET client program, which was not removed, would no longer operate. Likewise, removing TCP/IP by itself would cause the failure of both the TELNET and the FTP client programs. Also if we installed TCP/IP to support our own development, then installed the TELNET client (which depends on TCP/IP) and then still later removed the TELNET client, we would not want TCP/IP to be removed.

We want a program to automate the process of adding and removing components. To do this we will maintain a record of installed components and component dependencies. A component can be installed explicitly in response to a command (unless it is already installed), or implicitly if it is needed for some other component being installed. Likewise, a component, not explicitly installed, can be explicitly removed in response to a command (if it is not needed to support other components) or implicitly removed if it is no longer needed to support another component. Installing an already implicitly-installed component won't make that component become explicity installed.

Input

The input will contain a sequence of commands (as described below), each on a separate line containing no more than eighty characters. Item names are case sensitive, and each is no longer than ten characters. The command names (DEPEND, INSTALL, REMOVE and LIST) always appear in uppercase starting in column one, and item names are separated from the command name and each other by one or more spaces. All appropriate DEPEND commands will appear before the occurrence of any INSTALL command that uses them. There will be no circular dependencies. The end of the input is marked by a line containing only the word END.

Command Syntax	Interpretation/Response
DEPEND item1 item2 [item3 ...]	item1 depends on item2 (and item3 ...)
INSTALL item1	install item1 and those on which it depends
REMOVE item1	remove item1, and those on which it depends, if possible
LIST	list the names of all currently-installed components

Output

Echo each line of input. Follow each echoed INSTALL or REMOVE line with the actions taken in response, making certain that the actions are given in the proper order. Also identify exceptional conditions (see Sample Output, below, for examples of all cases). For the LIST command, display the names of the currently installed components in the installation order. No output, except the echo, is produced for a DEPEND command or the line containing END. There will be at most one dependency list per item.

Sample Input 1

DEPEND   TELNET TCPIP NETCARD
DEPEND TCPIP NETCARD
DEPEND DNS TCPIP NETCARD
DEPEND  BROWSER   TCPIP  HTML
INSTALL NETCARD
INSTALL TELNET
INSTALL foo
REMOVE NETCARD
INSTALL BROWSER
INSTALL DNS
LIST
REMOVE TELNET
REMOVE NETCARD
REMOVE DNS
REMOVE NETCARD
INSTALL NETCARD
REMOVE TCPIP
REMOVE BROWSER
REMOVE TCPIP
END

Sample Output 1

DEPEND   TELNET TCPIP NETCARD
DEPEND TCPIP NETCARD
DEPEND DNS TCPIP NETCARD
DEPEND  BROWSER   TCPIP  HTML
INSTALL NETCARD
  Installing NETCARD
INSTALL TELNET
  Installing TCPIP
  Installing TELNET
INSTALL foo
  Installing foo
REMOVE NETCARD
  NETCARD is still needed.
INSTALL BROWSER
  Installing HTML
  Installing BROWSER
INSTALL DNS
  Installing DNS
LIST
  NETCARD
  TCPIP
  TELNET
  foo
  HTML
  BROWSER
  DNS
REMOVE TELNET
  Removing TELNET
REMOVE NETCARD
  NETCARD is still needed.
REMOVE DNS
  Removing DNS
REMOVE NETCARD
  NETCARD is still needed.
INSTALL NETCARD
  NETCARD is already installed.
REMOVE TCPIP
  TCPIP is still needed.
REMOVE BROWSER
  Removing BROWSER
  Removing HTML
  Removing TCPIP
REMOVE TCPIP
  TCPIP is not installed.
END

Sample Input 2

DEPEND A B
INSTALL A
INSTALL B
REMOVE A
END

Sample Output 2

DEPEND A B
INSTALL A
  Installing B
  Installing A
INSTALL B
  B is already installed.
REMOVE A
  Removing A
  Removing B
END

Anagram

You are to write a program that has to generate all possible words from a given set of letters.

Example: Given the word "abc", your program should - by exploring all different combination of the three letters - output the words "abc", "acb", "bac", "bca", "cab" and "cba".

In the word taken from the input file, some letters may appear more than once. For a given word, your program should not produce the same word more than once, and the words should be output in alphabetically ascending order.

Input

The input file consists of several words. The first line contains a number giving the number of words to follow. Each following line contains one word. A word consists of uppercase or lowercase letters from A to Z. Uppercase and lowercase letters are to be considered different.

Output

For each word in the input file, the output file should contain all different words that can be generated with the letters of the given word. The words generated from the same input word should be output in alphabetically ascending order. An upper case letter goes before the corresponding lower case letter.

Sample Input

3
aAb
abc
acba

Sample Output

Aab
Aba
aAb
abA
bAa
baA
abc
acb
bac
bca
cab
cba
aabc
aacb
abac
abca
acab
acba
baac
baca
bcaa
caab
caba
cbaa

The Skyline Problem

Background

With the advent of high speed graphics workstations, CAD (computer-aided design) and other areas (CAM, VLSI design) have made increasingly effective use of computers. One of the problems with drawing images is the elimination of hidden lines -- lines obscured by other parts of a drawing.

The Problem

You are to design a program to assist an architect in drawing the skyline of a city given the locations of the buildings in the city. To make the problem tractable, all buildings are rectangular in shape and they share a common bottom (the city they are built in is very flat). The city is also viewed as two-dimensional. A building is specified by an ordered triple where and are left and right coordinates, respectively, of building i and is the height of the building. In the diagram below buildings are shown on the left with triples (1,11,5), (2,6,7), (3,13,9), (12,7,16), (14,3,25), (19,18,22), (23,13,29), (24,4,28)

the skyline, shown on the right, is represented by the sequence: (1, 11, 3, 13, 9, 0, 12, 7, 16, 3, 19, 18, 22, 3, 23, 13, 29, 0)

The Input

The input is a sequence of building triples. All coordinates of buildings are positive integers less than 10,000 and there will be at least one and at most 5,000 buildings in the input file. Each building triple is on a line by itself in the input file. All integers in a triple are separated by one or more spaces. The triples will be sorted by , the left x-coordinate of the building, so the building with the smallest left x-coordinate is first in the input file.

The Output

The output should consist of the vector that describes the skyline as shown in the example above. In the skyline vector , the such that i is an even number represent a horizontal line (height). The such that i is an odd number represent a vertical line (x-coordinate). The skyline vector should represent the ``path'' taken, for example, by a bug starting at the minimum x-coordinate and traveling horizontally and vertically over all the lines that define the skyline. Thus the last entry in the skyline vector will be a 0. The coordinates must be separated by a blank space.

Sample Input

1 11 5
2 6 7
3 13 9
12 7 16
14 3 25
19 18 22
23 13 29
24 4 28

Sample Output

1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0

Prime Ring Problem

A ring is composed of n (even number) circles as shown in diagram. Put natural numbers into each circle separately, and the sum of numbers in two adjacent circles should be a prime.

Note: the number of first circle should always be 1.

Input

n (0 < n <= 16)

Output

The output format is shown as sample below. Each row represents a series of circle numbers in the ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the above requirements.

You are to write a program that completes above process.

Sample Input

6
8

Sample Output

Case 1:
1 4 3 2 5 6
1 6 5 2 3 4

Case 2:
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2

The 3n + 1 problem

Background

Problems in Computer Science are often classified as belonging to a certain class of problems (e.g., NP, Unsolvable, Recursive). In this problem you will be analyzing a property of an algorithm whose classification is not known for all possible inputs.

The Problem

Consider the following algorithm:

 1.    input n

  2.    print n

  3.    if n = 1 then STOP

  4.       if n is odd then  

  5.       else  

  6.    GOTO 2

Given the input 22, the following sequence of numbers will be printed 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

It is conjectured that the algorithm above will terminate (when a 1 is printed) for any integral input value. Despite the simplicity of the algorithm, it is unknown whether this conjecture is true. It has been verified, however, for all integers n such that 0 < n <>

Given an input n, it is possible to determine the number of numbers printed (including the 1). For a given n this is called the cycle-length of n. In the example above, the cycle length of 22 is 16.

For any two numbers i and j you are to determine the maximum cycle length over all numbers between i and j.

The Input

The input will consist of a series of pairs of integers i and j, one pair of integers per line. All integers will be less than 1,000,000 and greater than 0.

You should process all pairs of integers and for each pair determine the maximum cycle length over all integers between and including i and j.

You can assume that no operation overflows a 32-bit integer.

The Output

For each pair of input integers i and j you should output i, j, and the maximum cycle length for integers between and including i and j. These three numbers should be separated by at least one space with all three numbers on one line and with one line of output for each line of input. The integers i and j must appear in the output in the same order in which they appeared in the input and should be followed by the maximum cycle length (on the same line).

Sample Input

1 10
100 200
201 210
900 1000

Sample Output

1 10 20
100 200 125
201 210 89
900 1000 174