Description

Consider an input string of length less than 1000. For example, " abcdefgabcdefg".

We may denote a substring of this input string by a pair of indexes. For example, the pair (5, 9) represents the substring "fgabc". (The index starts from 0, following the C convention.)

Now, given N pairs of the indexes representing N substrings, we are interested in sorting these substrings in alphabetical order. For example, if the five pairs are (8, 12), (7, 11), (6, 10), (4, 8), and (5, 9), then the corresponding substrings are "bcdef", "abcde", "gabcd", "efgab", "fgabc". The output of the sorted substrings would be

abcde
bcdef
efgab
fgabc
gabcd

Input

The first line contains an input string. The length of the input string is less than 1000.

The second line is an integer N indicating the number of substrings, where N<=100.

The next N lines are the N pairs of indexes denoting the N substrings. (The index of the first character in the input string is 0 as in the C array indexing convention.)

Output

The output contains N lines for the N sorted substrings. Each line should be ended with a newline character ' '.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Modify the code of ‘calculator.c’ (in 10469) to add two new capabilities.

1.   The capability of modulo operation ‘%’. You can add this feature in MULDIV, by jointly checking the token with the existing ones of multiplication and division.

For example, if the input is ‘4*7 % 5’, the output is 3. If the input is ‘3 + 8 % 5’, the output is 6

You need to

(1)   Add code dealing with ‘%’ in getToken().

(2)   Add the evaluation of ‘%’ in term().

2.   The capability of less than ‘<’ and greater than ‘>’

You need to

(1)   Add a new token in TokenSet, named LTGT a.k.a. less than or greater than.

(2)   In getToken(), add code to bind the input of ‘>’ and ‘<’ with LTGT.

(3)   Change some parts of the grammar as follows:

statement       := END | expr END
  expr            := add_expr   expr_tail
  expr_tail       := LTGT   add_expr   expr_tail | NIL
  add_expr        := term   add_expr_tail
  add_expr_tail   := ADDSUB   term     add_expr_tail | NIL
  term            := factor   term_tail
  term_tail       := MULDIV   factor   term_tail | NIL
  factor  := INT | ADDSUB INT | ADDSUB ID | ID ASSIGN expr | ID | LPAREN  expr RPAREN

The previous expression of ADDSUB is lowered by one level and changed its name to add_expr. Meanwhile, expr is used for dealing with LTGT.

When the algorithm is done, the program should be able to deal with the conditions of LTGT. If the condition of ‘less than’ (or ‘greater than’) is true, the output is 1; otherwise the output is 0.

For example, if the input is ‘1 + 2 > 2’, the output is 1. If the input is ‘5 + 4 < 3’, the output is 0.

 

Input

One expression which is ended with new line character.

Output

The answer of input expression. You are asked to add the new line character in the end.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

#include 
#include 
#include 
#include 

/*
Something like Python

>> y = 2
>> z = 2
>> x = 3*y + 4/(2*z)

*/


/*
the only type: integer
everything is an expression
  statement   := END | expr END
  expr        := term expr_tail
  expr_tail   := ADDSUB term expr_tail | NIL
  term        := factor term_tail
  term_tail := MULDIV factor term_tail | NIL
  factor      := INT | ADDSUB INT | ADDSUB ID | ID ASSIGN expr | ID | LPAREN expr RPAREN
*/

#ifndef __LEX__
#define __LEX__
#define MAXLEN 256
typedef enum {UNKNOWN, END, INT, ID, ADDSUB, MULDIV, ASSIGN,
LPAREN, RPAREN} TokenSet;
char lexeme[MAXLEN];

extern int match (TokenSet token);
extern void advance(void);
#endif // __LEX__

static TokenSet getToken(void);
static TokenSet lookahead = UNKNOWN;

TokenSet getToken(void)
{
    int i;
    char c;

    while ( (c = fgetc(stdin)) == ' ' || c== '\t' );  // deal with space

    if (isdigit(c)) {
        lexeme[0] = c;
        c = fgetc(stdin);
        i = 1;
        while (isdigit(c) && i
  
Input
  
  
Output
  
  
Sample Input  Download
  

    
  
  
Sample Output  Download
  

    
  
  
  
  
  
Tags
    

      
        
      
    
    
  

  

  

  

  

    Discuss